Problema 1
Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza arbitraria di 0 e 1, termina la sua esecuzione lasciando sul nastro il bit di parità.
Tale bit è 1 se e solo se vi sono un numero dispari di 1 nella sequenza iniziale; altrimenti vale 0.
NASTRO INIZIALE | NASTRO FINALE |
---|---|
1011100010 | 1 |
0001100101 | 0 |
0000 | 0 |
Problema 2
Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza arbitraria di 0 e 1, termina la sua esecuzione lasciando sul nastro un bit uguale a 1 se e solo se la sequenza è del tipo 0n1n0n, ovvero ci sono n simboli 0, poi n simboli 1 e infine n simboli 0, per un qualche intero n>0.
Altrimenti, il bit lasciato sul nastro è 0.
NASTRO INIZIALE | NASTRO FINALE |
---|---|
000111000 | 1 |
0011100 | 0 |
00100 | 0 |
Problema 3
Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza arbitraria di 0 e 1, termina la sua esecuzione lasciando sul nastro una sequenza finale ottenuta da quella iniziale raddoppiando gli 1.
NASTRO INIZIALE | NASTRO FINALE |
---|---|
0010110101 | 0011011110110110 |
1001 | 110011 |
0000 | 0000 |
Problema 4
Sia fissata a priori la sequenza binaria P = 10110.
Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza arbitraria di 0 e 1, termina la sua esecuzione lasciando sul nastro un bit uguale a 1 se e solo se la sequenza iniziale contiene P.
Altrimenti, il bit lasciato sul nastro è 0.
NASTRO INIZIALE | NASTRO FINALE |
---|---|
0100101101101 | 1 |
100010100 | 0 |
0100101101101010 | 1 |
Problema 5
Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza di simboli 0, 1, 2 e 3, termina la sua esecuzione lasciando sul nastro la sequenza finale contenente gli stessi elementi ordinati in maniera non decrescente.
NASTRO INIZIALE | NASTRO FINALE |
---|---|
20230321020320002301 | 00000000112222223333 |
001223 | 001223 |
322100 | 001223 |
Problema 6
Programmare una macchina di Turing che, dato un nastro iniziale contenente un intero X rappresentato con cifre decimali, termina la sua esecuzione lasciando sul nastro il risultato della moltiplicazione di X per 11 (in cifre decimali).
NASTRO INIZIALE | NASTRO FINALE |
---|---|
48273 | 531003 |
0 | 0 |
12 | 132 |
Problema 7
Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza arbitraria di 0 e 1, termina la sua esecuzione lasciando sul nastro un bit uguale a 1 se e solo se la sequenza iniziale è della forma xx, ovvero è una sequenza ripetuta due volte.
Altrimenti, il bit lasciato sul nastro è 0.
NASTRO INIZIALE | NASTRO FINALE |
---|---|
01110111 | 1 |
11011011 | 0 |
101101 | 1 |
Problema 8
Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza del tipo xSyRz (in cui x, y e z sono sequenze di simboli 0, 1 e 2, con x e y di uguale lunghezza), termina la sua esecuzione lasciando sul nastro la sola sequenza z in cui ciascun carattere di x è stato sostituito, ordinatamente, con il corrispondente carattere di y.
NASTRO INIZIALE | NASTRO FINALE |
---|---|
1S0R12212 | 02202 |
02S10R02201 | 10011 |
10S02R10012 | 22222 |
Problema 9
Programmare una macchina di Turing che, data una sequenza del tipo n1xn2yn3z… con ciascun numero ni>0 rappresentato con cifre decimali, termini lasciando sul nastro una sequenza di n1 simboli x seguiti da n2 simboli y, da n3 simboli z ecc.
Si assuma che i simboli x, y e z siano A, B o C.
NASTRO INIZIALE | NASTRO FINALE |
---|---|
3A2B1A | AAABBA |
1C2B1C3A | CBBCAAA |
10C | CCCCCCCCCC |