Dato un numero intero positivo n, (n div 2) è il quoziente della divisione intera.
Ad esempio, (6 div 2) è il numero 3, mentre (9 div 2) è il numero 4.
Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza composta da n A consecutive (con n > 1), termina la sua esecuzione lasciando sul nastro la sequenza composta da (n div 2) A consecutive.
Esempi
| Nastro iniziale | Nastro finale | |
|---|---|---|
| 1° | AAAA | AA |
| 2° | AAAAA | AA |
| 3° | AAA | A |
| 4° | AA | A |
Diagramma di stato
- Se legge due A consecutive va a destra, scrive X e ritorna a sinistra
- Altrimenti traduce le X in A e si ferma
Tabella delle transizioni di stato
| A | X | – | |
|---|---|---|---|
| 0 | 1, -, > | 0, A, > | |
| 1 | 2, -, > | 1, A, > | |
| 2 | 2, A, > | 2, X, > | R, X, < |
| R | R, A, < | R, X, < | 0, -, > |
Quintuple
(0, A, 1, -, >)
(0, X, 0, A, >)
(1, A, 2, -, >)
(1, X, 1, A, >)
(2, AX, 2, AX, >)
(2, -, R, X, <)
(R, AX, R, AX, <)
(R, -, 0, -, >)
- Ha letto la prima A
- Traduce le X in A
- Ha letto la seconda A
- Traduce le X in A
- Va a destra
- Scrive X
- Ritorna a sinistra
- Ricomincia