Esercizi di Gara della VI edizione

---

AVVISI:

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

• Per numero decimale si intende un numero positivo o nullo rappresentato con le cifre 0, 1, 2, ..., 9, senza zeri iniziali non significativi; per esempio 0 e 19 sono numeri validi, mentre 0032 deve essere scritto come 32.

• Nel fornire le soluzioni, ricordarsi di pulire il nastro finale da ogni simbolo che non costituisca la risposta!

• Ogni volta che si salva la soluzione di un esercizio con il simulatore della macchina di Turing, il “timestamp” dell’esercizio viene aggiornato con il tempo trascorso fino a quel momento.

Esercizio 1 [Punti 1]. Si vuole realizzare l’odometro di Erone da Alessandria, ovvero un contatore a cifre decimali a lunghezza fissa che incrementa di uno il numero N. Quando raggiunge il valore massimo 99…9, ritorna a 00…0. Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero decimale N, termini la sua esecuzione lasciando sul nastro l’incremento di N con l’odometro. Esempi:

NASTRO INIZIALE	NASTRO FINALE
3578	3579
10199	10200
999	000

Esercizio 2 [Punti 1]. Data una sequenza binaria, si vuole definire una operazione RUOTA che sposta ciclicamente lo 0 iniziale in fondo fino a che il bit iniziale è 1 (in caso di tutti 0, non fa nulla). Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza binaria di 0 e 1, applichi l’operazione RUOTA alla sequenza. Esempi:

NASTRO INIZIALE	NASTRO FINALE
000	000
1001011	1001011
000101001	101001000

Esercizio 3 [punti 1]. Nelle sequenze di DNA, composte dalla concatenazione dei simboli A, C, G e T, ciascun simbolo ha un proprio complemento. In particolare, il complemento per A, C, G e T è dato, rispettivamente, da T, G, C e A. Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza arbitraria di simboli A, C, G e T, appenda alla fine della sequenza una ulteriore sequenza con il complemento dei simboli. Esempi:

NASTRO INIZIALE	NASTRO FINALE
ATTCGACGATAT	ATTCGACGATATTAAGCTGCTATA
CCCCAAA	CCCCAAAGGGGTTT
ACGT	ACGTTGCA

Esercizio 4 [Punti 1]. Programmare una macchina di Turing che, dato un nastro iniziale contenente due sequenze di DNA (simboli A, C, G e T) di uguale lunghezza e separate da X, termini la sua esecuzione lasciando sul nastro il numero di posizioni in cui le due sequenze differiscono. Esempi:

NASTRO INIZIALE	NASTRO FINALE
AACGATXAAGGAC	2
AAXAA	0
ACACGTXCACAGT	4

Esercizio 5 [Punti 1]. Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero decimale N, termini la sua esecuzione lasciando sul nastro la sola sequenza SI se N è una potenza del due e la sola sequenza NO altrimenti. Esempi:

NASTRO INIZIALE	NASTRO FINALE
0	NO
128	SI
161	SI

Esercizio 6 [Punti 2]. Un insieme PQ di stringhe formate dai simboli P, Q e X soddisfa le seguenti proprietà:

• Le stringhe sPXQsX appartengono a PQ, per ogni sequenza s di X.

• Se sPtQz appartiene a PQ per le stringhe s, t e z di sole X, allora anche sPtXQzX appartiene a PQ.

Programmare una macchina di Turing che, dato un nastro iniziale contenente una stringa formata dai simboli P, Q e X, termina la sua esecuzione lasciando sul nastro la sola lettera S se la stringa appartiene all’insieme PQ, e la sola lettera N altrimenti. Esempi:

NASTRO INIZIALE	NASTRO FINALE
PXQX	S
XXXXXPXXQXXXXXXX	S
XXXXPXXQXXXXX	N

Esercizio 7 [Punti 2*]. Dati due numeri decimali maggiori o uguali a 0, separati da M, con il primo numero maggiore o uguale al secondo, si vuole calcolare la differenza. Programmare una macchina di Turing che, dato un nastro iniziale contenente i due numeri decimali separati dal simbolo M, termini la sua esecuzione lasciando sul nastro la loro differenza. Esempi:

NASTRO INIZIALE	NASTRO FINALE
120M4	116
373M373	0
1057M0	1057

Esercizio 8 [Punti 3]. Data una sequenza di DNA formata dai simboli A, C, G e T, si vuole ottenere la sua rappresentazione LRE sostituendo ogni stringa di simboli consecutivi uguali con un solo simbolo seguito dalla rappresentazione decimale della lunghezza della stringa (tale rappresentazione va omessa se la lunghezza è 1). Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza di DNA, termini la sua esecuzione lasciando sul nastro la sua rappresentazione LRE. Esempi:

NASTRO INIZIALE	NASTRO FINALE
AAACGGGGAAT	A3CG4A2T
CCCCCCCCCCCCCCA	C14A
ACGT	ACGT

Esercizio 9 [Punti 3]. La doppia inversione di una stringa si ottiene dividendo la stringa in due parti uguali (tranne il carattere centrale nel caso la stringa abbia lunghezza dispari) e invertendo l’ordine dei simboli in ciascuna parte. Programmare una macchina di Turing che, dato un nastro iniziale contenente una stringa di simboli A, B e C, termini la sua esecuzione lasciando sul nastro la doppia inversione della stringa. Esempi:

NASTRO INIZIALE	NASTRO FINALE
ABAABCCC	AABACCCB
ABCAB	BACBA
ACABAAA	ACABAAA

Esercizio 10 [Punti 3]. Si considerino le seguenti due operazioni M e S su un numero decimale. L’operazione M moltiplica il numero per 2, mentre l’operazione S somma 1. Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero decimale positivo N > 1, termini l’esecuzione lasciando sul nastro la più breve sequenza di operazioni M e S che produce N a partire da 2. Esempi:

NASTRO INIZIALE	NASTRO FINALE
4	M
2	(nastro vuoto)
12	SMM
43	MSMMSMS