Edizione I

Problema 1

Programmare una Macchina di Turing che, dato un nastro iniziale contenente la rappresentazione decimale di un numero intero positivo n, <> 0, termina la sua esecuzione lasciando sul nastro la rappresentazione decimale di n*100.

NASTRO INIZIALE	NASTRO FINALE
431	43100
6	600

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 una sola T se la sequenza iniziale contiene almeno una B, una sola F altrimenti.

NASTRO INIZIALE	NASTRO FINALE
BABBAB	T
B	T
AAA	F

Problema 3

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di cifre decimali, termina la sua esecuzione lasciando sul nastro la sequenza che si ottiene eliminando tutte le cifre 0 alla sinistra della cifra diversa da 0 più a sinistra.

Se la sequenza iniziale è composta da sole cifre 0, la macchina deve lasciare sul nastro un solo 0.

NASTRO INIZIALE	NASTRO FINALE
000431	431
0000	0
004031	4031
431	431

Problema 4

Una sequenza si dice palindroma se la sua lettura da sinistra verso destra è uguale alla sua lettura da destra verso sinistra.

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 è palindroma, la sola sequenza NO altrimenti.

NASTRO INIZIALE	NASTRO FINALE
ABABA	SI
ABBA	SI
BABBA	NO
A	SI

Problema 5

Indichiamo con AⁿB^m una sequenza del tipo A…AB…B.

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza del tipo AⁿB^m, con n>0 e m>0, termina la sua esecuzione lasciando sul nastro

• una sola A se n>m
• una sola B se m>n
• una sola C se n=m.

NASTRO INIZIALE	NASTRO FINALE
AAAABB	A
AAABBBBB	B
AAABBB	C

Problema 6

Indichiamo con s e t due generiche sequenze formate da A e B.

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza del tipo sCtC, termina la sua esecuzione lasciando sul nastro la sequenza SI se S e T sono uguali, la sequenza NO altrimenti.

NASTRO INIZIALE	NASTRO FINALE
ABACABAC	SI
BBBCBBBC	SI
BABACBBAC	NO
BBBCABC	NO

Problema 7

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B, con almeno una B, termina la sua esecuzione lasciando sul nastro la sequenza di sole B consecutive (cioè non separate da alcuno spazio) che si ottiene da quella iniziale eliminando tutte le A.

NASTRO INIZIALE	NASTRO FINALE
ABAABA	BB
BAAABABB	BBBB
BBB	BBB

Problema 8

Dato un numero intero positivo n, (n div 2) è il quoziente della divisione intera.
Ad esempio, (6 div 2) è il numero 3, mentre (9 div 2) è il numero 4.

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza composta da n A consecutive (con n > 1), termina la sua esecuzione lasciando sul nastro la sequenza composta da (n div 2) A consecutive.

NASTRO INIZIALE	NASTRO FINALE
AAAA	AA
AAAAA	AA
AAA	A
AA	A

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 sequenza che si ottiene da quella iniziale rimpiazzando due o più A consecutive con una sola A e due o più Bconsecutive con una sola B.

NASTRO INIZIALE	NASTRO FINALE
ABAABBBA	ABABA
BBAABBBAB	BABAB
AAA	A
BB	B