Wang B-machine explained

As presented by Hao Wang (1954, 1957), 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" (Minsky, 1967: 200). 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 (1954) the B-machine has at its command only 4 instructions:

• (1) → : Move tape-scanning head one tape square to the right (or move tape one square left), then continue to next instruction in numerical sequence;
• (2) ← : Move tape-scanning head one tape square to the left (or move tape one square right), 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" (jump, branch) to instruction "n": If scanned tape-square is marked then go to instruction "n" else (if scanned square is blank) continue to next instruction in numerical sequence.

A sample of a simple B-machine instruction is his example (p. 65):

1. *, 2. →, 3. C2, 4. →, 5. ←

He rewrites this as a collection of ordered pairs:

Wang's W-machine is simply the B-machine with the one additional instruction

• (5) E : In scanned tape-square erase the mark * (if there is one) then go to next instruction in numerical sequence.

See also

• Codd's cellular automaton
• Counter-machine model

References

• Hao Wang (1957), A Variant to Turing's Theory of Computing Machines, JACM (Journal of the Association for Computing Machinery) 4; 63–92. Presented at the meeting of the Association, June 23–25, 1954.
• Z. A. Melzak (1961) received 15 May 1961 An Informal Arithmetical Approach to Computability and Computation, Canadian Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 279–293. Melzak offers no references but acknowledges "the benefit of conversations with Drs. R. Hamming, D. McIlroy and V. Vyssotsky of the Bell telephone Laborators and with Dr. H. Wang of Oxford university."
• Joachim Lambek (1961) received 15 June 1961 How to Program an Infinite Abacus, Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 295–302. In his Appendix II, Lambek proposes a "formal definition of 'program'". He references Melzak (1961) and Kleene (1952) Introduction to Metamathematics.
• Marvin Minsky (1967), Computation: Finite and Infinite Machines, Prentice-Hall, Inc. Englewood Cliffs, N.J. In particular see p. 262ff (italics in original):

"We can now demonstrate the remarkable fact, first shown by Wang [1957], that for any Turing machine T there is an equivalent Turing machine T_N that never changes a once-written symbol! In fact, we will construct a two-symbol machine T_N that can only change blank squares on its tape to 1's but can not change a 1 back to a blank." Minsky then offers a proof of this.