Wang B-machine

From Wikipedia, the free encyclopedia

As proposed 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) p. 200). With only 4 sequential instructions it is very similar to, but even simpler than, the 7 sequential instructions of the Post-Turing machine.

The name "B-machine" has been used by Melzak (1961). He distinguishes it from C. Y Lee's "W-machine" which includes the ability to erase.

[edit] 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:

{ ( 1, * ), ( 2, → ), ( 3, C2 ), ( 4, → ), ( 5, ← ) }

[edit] 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 Arthmetical 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. Vyssots 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 Mathematics.
• 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 Tn that never changes a once-written symbol! In fact, we will construct a two-symbol machine Tn 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.