1. Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero intero n>0, termina la sua esecuzione lasciando sul nastro il numero n-1.

Esempi

nastro iniziale	nastro finale
14	13
1	0
200	199

 

2. 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 n A consecutive.

Esempi

nastro iniziale	nastro finale
1	A
5	AAAAA
9	aaaaaaaaa

 

3. 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.

Esempi

nastro iniziale	nastro finale
A	1
AAAAAA	6
AAAAAAAAAAA	11

 

4. 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 9>=y>0, termina la sua esecuzione lasciando sul nastro soltanto la differenza tra x e y.

Esempi

nastro iniziale	nastro finale
9-4	5
13-6	7
302-3	299

 

5. 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.

Esempi

nastro iniziale	nastro finale
ABcAB	CBB
BBABC	ABC
BA

 

 

 

6. 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.

Esempi

nastro iniziale	nastro finale
AADA	AA
AADAAA	AAA
AADAA DA	AA A

 

7. 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.

Esempi

nastro iniziale	nastro finale
ABADBAA	SI
BABADABBA	SI
ABBDBAA ABADABB	NO NO

 

8. 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.

Esempi

nastro iniziale	nastro finale
3	SI
27	SI
81	SI
20	NO
7676585	NO

 

9. Una sequenza di parentesi si dice bilanciata secondo la seguente definizione induttiva:

nastro iniziale	nastro finale
BEBE	SI
BBBEEE	SI
BBEBEE BBBEBEEBEE	SI SI
BEE	NO
BBEEEB	NO