boxes acting as an unbounded bitstring memory, and the set of instructions constituting a program.

Wang machines

In an influential paper, Hao Wang reduced Post's "formulation 1" to machines that still use a two-way infinite binary tape, but whose instructions are simpler - being the "atomic" components of Post's instructions - and are by default executed sequentially (like a "computer program"). His stated principal purpose was to

1.Previous
3.Next