Wang B-machine

Wang B-machine

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) 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. 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.


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, ← ) }

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.


*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.

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Wang tile — Wang tiles (or Wang dominoes), first proposed by mathematician Hao Wang in 1961, are a class of formal systems. They are modelled visually by equal sized squares with a color on each edge which can be arranged side by side (on a regular square… …   Wikipedia

  • Wang Jian (Qin) — Wang Jian (zh sp |s=王翦 |p=Wǎng jiǎn;) (year of birth and death unknown), a military leader of Qin (state) in the Warring States Period. He was born in Guanzhong county, city of Pinyang, Dongxiang village (now as the northeast of Fuping in Shǎnxī… …   Wikipedia

  • Wang Sichao — (王思潮) is a Chinese astronomy scholar, minor planet specialist, astronomer, and ufologist. cite web| title =Half of China sees mysterious light emitting UFO| publisher =UFO Evidence| month =July | year =2002| url… …   Wikipedia

  • Wang Laboratories — Infobox Company company name = Wang Laboratories company company type = Incorporation foundation = Cambridge, Massachusetts, USA (1951) location = Tewksbury, Massachusetts , USA (1963–1976) Lowell, Massachusetts, USA (1976–1997) key people = Dr.… …   Wikipedia

  • Wang Zhen (official) — This article is about Wang Zhen, agronomist and inventor. For other historical figures with this name, see Wang Zhen (disambiguation). Wang Zhen (zh tspw|t=王禎|s=王祯|p=Wáng Zhēn|w=Wang Chen, fl. 1290 1333) was an official of the Yuan Dynasty (1271… …   Wikipedia

  • Machine à remonter le temps — Voyage dans le temps Cet article fait partie de la série Science fiction La SF à l’écran autre A B C …   Wikipédia en Français

  • Machine à voyager dans le temps — Voyage dans le temps Cet article fait partie de la série Science fiction La SF à l’écran autre A B C …   Wikipédia en Français

  • Register machine — In mathematical logic and theoretical computer science a register machine is a generic class of abstract machines used in a manner similar to a Turing machine. All the models are Turing equivalent. Contents 1 Overview 2 Formal definition 3 …   Wikipedia

  • Turing machine equivalents — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… …   Wikipedia

  • Post–Turing machine — The article Turing machine gives a general introduction to Turing machines, while this article covers a specific class of Turing machines. A Post–Turing machine is a program formulation of an especially simple type of Turing machine, comprising a …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”