Problema 1
Programmare una Macchina di Turing che, dato un nastro iniziale contenente la rappresentazione decimale di un numero intero positivo k, termina la sua esecuzione lasciando sul nastro la sola sequenza SI se k è un numero pari, la sola sequenza NO altrimenti.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| 148 | SI |
| 2763 | NO |
Problema 2
Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B, termina la sua esecuzione lasciando sul nastro la sola sequenza SI se la sequenza iniziale contiene la sottosequenza ABA, la sola sequenza NO altrimenti.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| AABAB | SI |
| ABBA | NO |
| BA | NO |
Problema 3
Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B di lunghezza dispari, termina la sua esecuzione lasciando sul nastro il simbolo in posizione centrale della sequenza iniziale.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| AABAB | B |
| AAA | A |
| B | B |
Problema 4
Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B termina la sua esecuzione lasciando sul nastro la sequenza ottenuta rovesciando quella iniziale.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| AABAB | BABAA |
| ABA | ABA |
| A | A |
Problema 5
Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di sole A, termina la sua esecuzione lasciando sul nastro una sequenza di A e B intercalate, di lunghezza doppia rispetto alla sequenza iniziale.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| AA | ABAB |
| AAA | ABABAB |
| A | AB |
Problema 6
Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza, eventualmente vuota, contenente un numero pari di A, termina la sua esecuzione lasciando sul nastro la sequenza ottenuta da quella iniziale inserendo al centro della stessa la sequenza BB.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| AA | ABBA |
| AAAA | AABBAA |
| BB |
Problema 7
Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A, B e C termina la sua esecuzione lasciando sul nastro la sequenza ottenuta da quella iniziale rimpiazzando ogni sottosequenza ABC con ACB.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| AABCC | AACBC |
| ABCABCA | ACBACBA |
| ACAB | ACAB |
Problema 8
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 sequenza contenente lo stesso numero di A e lo stesso numero di B della sequenza iniziale, in cui però tutte le A precedono tutte le B.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| ABBAB | AABBB |
| BABAAA | AAAABB |
| AAB | AAB |
Problema 9
Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B termina la sua esecuzione lasciando sul nastro la sola sequenza SI se la sequenza iniziale contiene un numero pari di A e un numero dispari di B, la sola sequenza NO altrimenti.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| ABBAB | SI |
| BBABAA | NO |
| BABA | NO |
| BBB | SI |
Problema 10
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 A se, nella sequenza iniziale, il numero di A è maggiore o uguale del numero di B, una sola B altrimenti.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| ABABA | A |
| BBAA | A |
| BABBA | B |
| BB | B |