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
Quintuple
(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 |