Se non specificato altrimenti, negli esercizi le sequenze iniziali si intendono non vuote, ovvero contenenti almeno un simbolo.

• Programmare una Macchina di Turing che, dato un nastro iniziale contenente la rappresentazione decimale di un numero intero positivo k, termina la sua esecuzione lasciando sul nastro la sola sequenza SI se k è un numero pari, la sola sequenza NO altrimenti.

Esempi

nastro iniziale	nastro finale
148	SI
2763	NO

• 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 contiene la sottosequenza ABA, la sola sequenza NO altrimenti.


Esempi

nastro iniziale	nastro finale
AABAB	SI
ABBA	NO
BA	NO

• Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B di lunghezza dispari, termina la sua esecuzione lasciando sul nastro il simbolo in posizione centrale della sequenza iniziale.

Esempi

nastro iniziale	nastro finale
AABAB	B
AAA	A
B	B

• 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 ottenuta rovesciando quella iniziale.

Esempi

nastro iniziale	nastro finale
AABAB	BABAA
ABA	ABA
A	A

• Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di sole A, termina la sua esecuzione lasciando sul nastro una sequenza di A e B intercalate, di lunghezza doppia rispetto alla sequenza iniziale.

Esempi

nastro iniziale	nastro finale
AA	ABAB
AAA	ABABAB
A	AB

• Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza, eventualmente vuota, contenente un numero pari di A, termina la sua esecuzione lasciando sul nastro la sequenza ottenuta da quella iniziale inserendo al centro della stessa la sequenza BB.

Esempi

nastro iniziale	nastro finale
AA	ABBA
AAAA	AABBAA
	BB

• Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A, B e C termina la sua esecuzione lasciando sul nastro la sequenza ottenuta da quella iniziale rimpiazzando ogni sottosequenza ABC con ACB.
Esempi

nastro iniziale	nastro finale
AABCC	AACBC
ABCABCA	ACBACBA
ACAB	ACAB

• 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 sequenza contenente lo stesso numero di A e lo stesso numero di B della sequenza iniziale, in cui però tutte le A precedono tutte le B.

Esempi

nastro iniziale	nastro finale
ABBAB	AABBB
BABAAA	AAAABB
AAB	AAB

• 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 contiene un numero pari di A e un numero dispari di B, la sola sequenza NO altrimenti.

Esempi

nastro iniziale	nastro finale
ABBAB	SI
BBABAA	NO
BABA	NO
BBB	SI

• 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 A se, nella sequenza iniziale, il numero di A è maggiore o uguale del numero di B, una sola B altrimenti.