VI edizione

Odometro di Erone1

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.

Ruota zeri1

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.

ComplementoSequenzaDNA1

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.

Differenze tra sequenze DNA1

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.

Potenza del 21

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.

Sequenza PQ2

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.

Differenza2

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.

Accorpa Sequenza ACGT3

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.

Doppia inversione3

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.

Operazioni MS3

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.