Macchina di Turing che incrementa 2 volte un n° decimale presente su un nastro
Stato iniziale : la testina di lettura e scrittura è posizionata sulla cifra meno significativa.
Stato finale : la testina di lettura e scrittura è posizionata sulla cifra meno significativa.
Matrice funzionale
| b |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
0 |
|
| qo |
b q3 dx |
3 q3 dx |
4 q3 dx |
5 q3 dx |
6 q3 dx |
7 q3 dx |
8 q3 dx |
9 q3 dx |
0 q1 sx |
1 q1 sx |
2 q3 dx |
| q1 |
1 q2 dx |
2 q2 dx |
3 q2 dx |
4 q2 dx |
5 q2 dx |
6 q2 dx |
7 q2 dx |
8 q2 dx |
9 q2 dx |
0 q1 sx |
1 q2 dx |
| q2 |
b q3 sx |
1 q2 dx |
2 q2 dx |
3 q2 dx |
4 q2 dx |
5 q2 dx |
6 q2 dx |
7 q2 dx |
8 q2 dx |
9 q2 dx |
0 q2 dx |
| q3 |
dove gli stati hanno i seguenti significati :
q0 Þ elaborazione della 1ª cifra.
q1 Þ elaborazione della 2ª cifra e se questa è 9, della successiva.
q2 Þ riposizionamento sulla cifra meno significativa del n° risultante.
q3 Þ stop.
Esempio di computazione della stringa
|
|
b |
9 |
9 |
9 |
b |
b |
T.L.S.
| 9 |
9 |
q0 |
9 |
|||
| 9 |
q1 |
9 |
1 |
|||
| b |
q1 |
9 |
0 |
1 |
||
| b |
q1 |
b |
0 |
0 |
1 |
|
| 1 |
q2 |
0 |
0 |
1 |
||
| 1 |
0 |
q2 |
0 |
1 |
||
| 1 |
0 |
0 |
q2 |
1 |
||
| 1 |
0 |
0 |
1 |
q2 |
b |
|
| 1 |
0 |
0 |
q3 |
1 |