Wang B-machine


As presented by Hao [Wang (academic)|Hao Wang], his basic machine B is an extremely simple computational model equivalent to the Turing machine. It is "the first formulation of a Turing-machine theory in terms of computer-like models". With only 4 sequential instructions it is very similar to, but even simpler than, the 7 sequential instructions of the Post–Turing machine. In the same paper, Wang introduced a variety of equivalent machines, including what he called the W-machine, which is the B-machine with an "erase" instruction added to the instruction set.

Description

As defined by Wang the B-machine has at its command only 4 instructions:
  1. → : Move tape-scanning head one tape square to the right, then continue to next instruction in numerical sequence;
  2. ← : Move tape-scanning head one tape square to the left, then continue to next instruction in numerical sequence;
  3. * : In scanned tape-square print mark * then go to next instruction in numerical sequence;
  4. Cn: Conditional "transfer" to instruction "n": If scanned tape-square is marked then go to instruction "n" else continue to next instruction in numerical sequence.
A sample of a simple B-machine instruction is his example:
He rewrites this as a collection of ordered pairs:
Wang's W-machine is simply the B-machine with the one additional instruction