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 |
|---|---|
| AAAA | AA |
| AAAAA | AA |
| AAA | A |
| AA | A |
Algoritmo
- Se legge due A consecutive va a destra, scrive X e ritorna a sinistra
- Altrimenti traduce le X in A e si ferma
| Codice | Commenta |
|---|---|
(0,A,1,-,>) | Ha letto la prima A |
(0,X,0,A,>) | Traduce le X in A |
(1,A,2,-,>) | Ha letto la seconda A |
(1,X,1,A,>) | Traduce le X in A |
(2,AX,2,AX,>) | Va a destra |
(2,-,R,X,<) | Scrive X |
(R,AX,R,AX,<) | Ritorna a sinistra |
(R,-,0,-,>) | Ricomincia |