XII edizione

Notazione unaria3

Un numero intero n è rappresentato in notazione unaria da una sequenza di n simboli uguali, per esempio U. Si scriva un programma per macchina di Turing che, ricevuto sul nastro un intero positivo in notazione decimale, lasci come risultato lo stesso numero, scritto in notazione unaria.

Inversione5

Si scriva un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa sull'alfabeto {H, O, C} (attenzione: si tratta della lettera O, non della cifra 0), lasci sul nastro alla fine della computazione la stessa stringa, ma scritta in ordine inverso.Si scriva un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa sull'alfabeto {H, O, C} (attenzione: si tratta della lettera O, non della cifra 0), lasci sul nastro alla fine della computazione la stessa stringa, ma scritta in ordine inverso.

Completezza4

Si scriva un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa sull'alfabeto {H, O, C}, lasci sul nastro la scritta SI se la stringa in ingresso conteneva ciascuno dei caratteri dell'alfabeto almeno una volta (la stringa in questo caso si dice completa rispetto all'alfabeto), NO in caso contrario.

Ordinamento7

Si scriva un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa sull'alfabeto {H, O, C}, lasci sul nastro una stringa composta dagli stessi simboli presenti nell'input, ciascuno con lo stesso numero di occorrenze, ma ordinati in modo che tutte le H precedano le O, e tutte le O precedano le C.

La chimica di Turing I12

Usiamo i caratteri H, O, C per rappresentare, rispettivamente, un atomo di idrogeno, ossigeno, carbonio. Una sequenza di queste lettere può quindi rappresentare una molecola (ovviamente è anche possibile scrivere formule che non possono rappresentare una molecola stabile, ma per semplicità non ci poniamo il problema). Nella chimica di Turing si usa una notazione compatta per scrivere queste formula, consistente in un numero decimale preceduto dalla lettera che identifica una molecola. Per esempio, O2 (ossigeno molecolare) sta per OO, CH4 (metano) per CHHHH e H2O (acqua) per HHO. Si scriva un programma per macchina di Turing che, ricevuto in ingresso una formula in notazione compatta, lasci sul nastro la stessa formula in notazione espansa. Si assuma per semplicità che le quantità siano sempre espresse da una sola cifra decimale (da 2 a 9; l'assenza di un numero indica 1).

La chimica di Turing II15

Come ulteriore forma di compressione, una formula in notazione compatta può essere preceduta da un numero decimale, che indica quante volte la formula è ripetuta. Per esempio, 2H2O (due molecole di acqua) sta per HHOHHO, e 4CO2 (quattro molecole di anidride carbonica) sta per COOCOOCOOCOO. Si scriva un programma per macchina di Turing per effettuare il cambio di notazione, con l'assunzione che il numero iniziale (che rappresenta il numero di molecole) sia compreso fra 2 e 9 (estremi inclusi), oppure assente del tutto.

Successione di Fibonacci15

I numeri di Fibonacci sono definiti, per ricorrenza, dalla seguente equazione:

f(x) = 1, se x <= 2

f(x) = f(x-1)+f(x-2), altrimenti

La successione di Fibonacci è formata dai numeri di Fibonacci consecutivi, partendo da f(1) (si noti che ogni termine della successione dopo i primi due è dato dalla somma dei due termini precedenti). Si scriva un programma per macchina di Turing che, dato in ingresso un numero decimale n, lasci in uscita sul nastro i primi n termini della successione di Fibonacci, separati esattamente da uno spazio.

Successione di Collatz22

Si consideri la funzione

c(x) = 3x+1, se x è dispari

c(x) = x/2, se x è pari

Si scriva un programma per macchina di Turing che, ricevuto sul nastro un intero x, lasci sul nastro la sequenza x c(x) c(c(x)) c(c(c(x))) ... 1 (con i valori separati da un singolo spazio). Si noti che, benché i valori della successione così ottenuta crescano e decrescano in maniera apparentemente imprevedibile, esiste una congettura (non un teorema), detta Congettura di Collatz, secondo la quale per qualunque valore iniziale x, la successione raggiunge prima o poi il valore 1. La lunghezza della sequenza è anch'essa molto variabile: per x=26, occorrono 11 passi per giungere a 1, ma per x=27 ne occorrono ben 111. La congettura è stata verificata su calcolatore per tutti gli interi x fino a circa 2,88·1018, ma manca una dimostrazione che ne garantisca la verità per qualunque x. Sarete voi a trovarla?

La chimica di Turing III35

Una formula stechiometrica di Turing è un'equazione, i cui termini sono separati dal simbolo =, e ciascuno dei termini è formato da una somma di molecole, in cui ogni addendo è una formula in notazione compatta (es.: 2H2O). Una formula di questo tipo si dice bilanciata se il numero totale di occorrenze di ogni elemento a destra e a sinistra del segno di uguale è identico. Per esempio, 2H2O+O2+H+H=2O2+4H è bilanciata (sono presenti 4 atomi di ossigeno e 4 di idrogeno in entrambi i termini), così come CH4+2O2=CO2+2H2O (che rappresenta la combustione del metano in presenza di ossigeno, e produce anidride carbonica e acqua), mentre CO2+H2O=4CHO non lo è. Si scriva un programma per macchina di Turing che, ricevuta in ingresso una stringa rappresentante una formula stechiometrica, lasci sul nastro la scritta SI se la formula è bilanciata, NO altrimenti.

La chimica di Turing IV30

In tempi di crisi energetica, si cerca di estrarre idrocarburi dalle fonti più variegate. Siamo interessati in particolare al metano, che ha formula CH4. Si scriva un programma per macchina di Turing che, ricevuta in input un termine di una formula stechiometrica (gli "ingredienti"), lasci sul nastro il numero di molecole di metano che sarebbe potenzialmente possibile estrarre dagli ingredienti. Per esempio, 8CO2+8H2O contiene 8 atomi di carbonio e 16 di idrogeno (oltre a 24 di ossigeno, che però non ci interessano); sarebbe quindi possibile estrarre da questi ingredienti fino a 4 molecole di metano (ovvero, 4 atomi di carbonio e 16 di idrogeno). Si noti che il numero di molecole di metano estraibili da una formula potrebbe richiedere più cifre decimali per essere espresso.