Wang B-machine
 | This article includes a list of references, but its sources remain unclear because it has insufficient inline citations. (August 2019) (Learn how and when to remove this template message) |
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;
- ← : Move tape-scanning head one tape square to the left (or move tape one square right), then continue to next instruction in numerical sequence;
- * : In scanned tape-square print mark * then go to next instruction in numerical sequence;
- 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:[2]
- 1. *, 2. →, 3. C2, 4. →, 5. ←
He rewrites this as a collection of ordered pairs:
- { ( 1, * ), ( 2, → ), ( 3, C2 ), ( 4, → ), ( 5, ← ) }
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
Notes
References
- Wang, Hao (1957). "A Variant to Turing's Theory of Computing Machines". Journal of the Association for Computing Machinery 4: 63–92. doi:10.1145/320856.320867. "Presented at the meeting of the Association, June 23–25, 1954".
- Melzak, Z. A. (September 1961). "An Informal Arithmetical Approach to Computability and Computation". Canadian Mathematical Bulletin 4 (3): 279–293. doi:10.4153/CMB-1961-031-9. "Received 15 May 1961. 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."".
- Lambek, Joachim (September 1961). "How to Program an Infinite Abacus". Canadian Mathematical Bulletin 4 (3): 295–302. doi:10.4153/CMB-1961-032-6. "Received 15 June 1961. Appendix II proposes a formal definition of “program”; references (Melzak 1961) and Kleene (1952) Introduction to Metamathematics.".
- Minsky, Marvin Lee (1967). Computation: Finite and Infinite Machines. Englewood Cliffs, NJ: Prentice-Hall. pp. 262–264. ISBN 9780131655638. "(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."
 |  |
