Edizione IV

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 0ⁿ1ⁿ0ⁿ, 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 n₁xn₂yn₃z… con ciascun numero n_i>0 rappresentato con cifre decimali, termini lasciando sul nastro una sequenza di n₁ simboli x seguiti da n₂ simboli y, da n₃ 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

Problema 10

Vedi discussione…