Máquina Wang-b

Concebida por Hao Wang (1954, 1957), a simples máquina B é um simples modelo computacional equivalente a Máquina de Turing.Esta é "a primeira formulação da teoria da máquina de turing utilizando computadores como modelo" (Minsky (1967) p. 200). Com apenas 4 instruções, ela é bem similar, porém sendo mais simples, as 7 instruções da Post-Turing machine. Com a mesma finalidade, Wang introduziu uma variedade de máquinas equivalentes, incluindo a nomeada por ele de Máquina-B, que é a Máquina-B com uma instrução "apagar" adicionada ao conjunto de instruções

Descrição

Definida por Wang (1954) a Máquina-B possui apenas 4 instruções:

• (1) → : Move a cabeça da fita para a direita (ou move a fita para a esquerda), então continua para a próxima instrução seguindo a sequencia numérica;
• (2) ← : Move a cabeça da fita para a esquerda (ou a fita para a direita), então continua para a próxima instrução seguindo a sequencia numérica;
• (3) * : Marque * na posição atual da fita, então continue para a próxima instrução seguindo a sequência numérica;
• (4) Cn: Salto condicional para a instrução "n": Se a posição atual da fita está marcada, então vá para a instrução "n" se não estiver marcada continue para a próxima instrução seguindo a sequencia numérica

Uma simples instrução de uma Máquina-B (p. 65):

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

Ele reescreve isto como uma coleção de pares ordenados:

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

A máquina-W de Wang é uma Máquina-B simples, com uma instrução adicional

• (5) E : Na posição atual da fita, apague a marcação * (se existe), então continue para a próxima instrução seguindo a sequência numérica.

Veja Também

• Codd's cellular automaton

Referências

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