Edizione III

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:

1. la sequenza vuota è bilanciata,
2. 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