Macchina di Turing > Macchina a Registri
Dalla macchina di Turing con
- N simboli
- un nastro infinito
- binaria
- dotata di RAM, ROM, dispositivi di I/O...
Ad ogni passo si può dimostrare l'equivalenza tra le due macchine
| Da | A | ||
|---|---|---|---|
| Nastro infinito | N simboli | Nastro infinito | 2 simboli |
| Nastro infinito | 2 simboli | Nastro Semi-Infinito | 8 simboli |
| Nastro semi-infinito | 8 simboli | Nastro semi-infinito | 2 simboli |
| M nastri | 2 simboli | 1 nastro | 2M simboli |
| Un nastro | 2M simboli | Un nastro di parole (di lunghezza M) | 2 simboli |
| Nastro semi-infinito (ad accesso sequenziale) | Nastro semi-infinito ad accesso casuale (R.A.M.) | ||
| Un nastro (R.A.M.) | N nastri (R.A.M., R.O.M., dispositivi di I/O, …) | ||
