Problema 1
Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero intero n compreso tra 1 e 9, termina la sua esecuzione lasciando sul nastro A…A (n consecutive).
NASTRO INIZIALE | NASTRO FINALE |
---|---|
1 | A |
5 | AAAAA |
9 | AAAAAAAAA |
Problema 2
Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza di n A consecutive (con n>0), termina la sua esecuzione lasciando sul nastro il numero n.
NASTRO INIZIALE | NASTRO FINALE |
---|---|
A | 1 |
AAAAAA | 6 |
AAAAAAAAAAA | 11 |
Problema 3
Programmare una macchina di Turing che, dato un nastro iniziale contenente due numeri interi positivi x e y separati da una cella vuota tali che x>y e 0<y<=9, termina la sua esecuzione lasciando sul nastro soltanto la differenza tra x e y.
NASTRO INIZIALE | NASTRO FINALE |
---|---|
9 4 | 5 |
13 6 | 7 |
302 3 | 199 |
Problema 4
Indichiamo con S una sequenza formata da A, B o C ed indichiamo con x e y un simbolo che sia A o B.
Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza del tipo xyS termina la sua esecuzione lasciando sul nastro la sequenza ottenuta da S rimpiazzando tutte le occorrenze di x con y.
NASTRO INIZIALE | NASTRO FINALE |
---|---|
ABCAB | CBB |
BBABC | ABC |
BA |
Problema 5
Programmare una macchina di Turing che, dato un nastro iniziale contenente due sequenze di A separate da una D, termina la sua esecuzione lasciando sul nastro la sequenza che contiene il maggior numero di A.
NASTRO INIZIALE | NASTRO FINALE |
---|---|
AADA | AA |
AADAAA | AAA |
AADAA | AA |
DA | A |
Problema 6
Indichiamo con S e T due sequenze non vuote e della stessa lunghezza formate da A o B.
Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza del tipo SDT, termina la sua esecuzione lasciando sul nastro nastro la sola sequenza SI se T è un anagramma di S, la sola sequenza NO altrimenti.
NASTRO INIZIALE | NASTRO FINALE |
---|---|
ABADBAA | SI |
BABADABBA | SI |
ABBADBAA | NO |
ABADABB | NO |
Problema 7
Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero intero (arbitrariamente grande), termina la sua esecuzione lasciando sul nastro la sola sequenza SI se il numero è divisibile per 3, la sola sequenza NO altrimenti.
NASTRO INIZIALE | NASTRO FINALE |
---|---|
3 | SI |
27 | SI |
81 | SI |
20 | NO |
7676585 | NO |
Problema 9
Una sequenza di parentesi si dice bilanciata secondo la seguente definizione induttiva:
- la sequenza vuota è bilanciata,
- se S e T sono sequenze bilanciate allora anche la sequenza (S)T è bilanciata.
Rappresentando ( con B e ) con E, programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza di B ed E, termina la sua esecuzione lasciando sul nastro la sola sequenza SI se la sequenza è bilanciata, la sola sequenza NO altrimenti.
NASTRO INIZIALE | NASTRO FINALE |
---|---|
BEBE | SI |
BBBEEE | SI |
BBBEEE | SI |
BBBEBEEBEE | SI |
BEE | NO |
BBBEEB | NO |