Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B, termina la sua esecuzione lasciando sul nastro una sola T se la sequenza iniziale contiene almeno una B, una sola F altrimenti.
Esempi
| Nastro iniziale | Nastro finale | |
|---|---|---|
| 1° | BABBAB | T |
| 2° | B | T |
| 3° | AAA | F |
Si tratta dell’operazione OR su una sequenza di A e B invece che 0 e 1
Diagramma di stato
- Lo stato 0 indica che non c’è alcuna B e se l’input finisce scrive F
- Lo stato 1 indica che c’è almeno una B e se l’input finisce scrive T
Tabella delle transizioni di stato
| A | B | – | |
|---|---|---|---|
| 0 | 0, -, > | 1, -, > | H, F, - |
| 1 | 1, -, > | 1, -, > | H, T, - |
| H | — | — | — |
Quintuple #1
(0, A, 0, -, >)
(0, B, 1, -, >)
(0, -, H, F, >)
(1, A, 1, -, >)
(1, B, 1, -, >)
(1, -, H, T, >)
- Finché legge A rimane in 0
- Se legge B va in 1
- Se l’input è finito scrive F
- Finché legge A rimane in 1
- Finché legge B rimane in 1
- Se l’input è finito scrive T
Quintuple #2
(0, A, 0, -, >)
(0, B, 1, -, >)
(0, -, H, F, >)
(1, [AB], 1, -, >)
(1, -, H, T, >)