Macchina B di Wang
# 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.
