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
|