Edizione VI

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

NASTRO INIZIALE	NASTRO FINALE
3578	3579
10199	10200
999	000

Problema 2

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.

NASTRO INIZIALE	NASTRO FINALE
000	000
1001011	1001011
000101001	101001000

Problema 3

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.

NASTRO INIZIALE	NASTRO FINALE
ATTCGACGATAT	ATTCGACGATATTAAGCTGCTATA
CCCCAAA	CCCCAAAGGGGTTT
ACGT	ACGTTGCA

Problema 4

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.

NASTRO INIZIALE	NASTRO FINALE
AACGATXAAGGAC	2
AAXAA	0
ACACGTXCACAGT	4

Problema 5

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.

NASTRO INIZIALE	NASTRO FINALE
0	NO
128	SI
161	NO

Problema 6

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.

NASTRO INIZIALE	NASTRO FINALE
PXQX	S
XXXXXPXXQXXXXXXX	S
XXXXPXXQXXXXX	N

Problema 7

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.

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

Problema 8

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.

NASTRO INIZIALE	NASTRO FINALE
AAACGGGGAAT	A3CG4A2T
CCCCCCCCCCCCCCA	C14A
ACGT	ACGT

Problema 9

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.

NASTRO INIZIALE	NASTRO FINALE
ABAABCCC	AABACCCB
ABCAB	BACBA
ACABAAA	ACABAAA

Problema 10

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.

NASTRO INIZIALE	NASTRO FINALE
4	M
2
12	SMM
43	MSMMSMS