Macchina B di Wang

La macchina B di Wang, enunciata dal logico e matematico Wang Hao, è un modello computazionale estremamente semplice, equivalente alla macchina di Turing. È "la prima formulazione di una teoria della macchina di Turing in termini di modelli simili al computer". Con solo 4 istruzioni sequenziali è molto simile, ma anche più semplice, delle 7 istruzioni sequenziali della macchina di Post-Turing (una variante della macchina di Turing). Nello stesso articolo, Wang ha introdotto una varietà di macchine equivalenti, compresa quella che ha chiamato "macchina W", che ha un'istruzione "cancella" aggiunta al gruppo di istruzioni.

Descrizione

Come definita da Wang, nel 1954, la macchina B dispone di solo 4 istruzioni:

• (1) → : Spostare la testina di scansione del nastro nell'area di nastro a destra (o spostare l'area del nastro a sinistra), quindi continuare con l'istruzione successiva in sequenza numerica;
• (2) ← : Spostare la testina di scansione del nastro nell'area di nastro a sinistra (o spostare l'area del nastro a destra), quindi continuare con l'istruzione successiva in sequenza numerica;
• (3) * : Nell'area di nastro scansionata premere il tasto * e poi passare all'istruzione successiva in sequenza numerica;
• (4) Cn: "Trasferimento" condizionale (salta, diramazione) all'istruzione "n": se l'area del nastro scansionato è segnata, passare all'istruzione "n" altrimenti (se l'area del nastro è vuota) continuare con l'istruzione successiva in sequenza numerica.

Un esempio delle istruzione di cui sopra:

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

Egli lo riscrisse come una raccolta di coppie ordinate:

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

La macchina W di Wang è semplicemente la macchina B con un'istruzione aggiuntiva

• (5) E : Nell'area di nastro scansionata cancella il segno * (se presente) quindi andare alle istruzioni successive in sequenza numerica.

Bibliografia

• Wang Hao (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, Doug McIlroy and Victor A. 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.