Problema 1 – Notazione unaria
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.
| NASTRO INIZIALE | NASTRO FINALE |
| 4 | UUUU |
|---|---|
| 0 | |
| 13 | UUUUUUUUUUUUU |
| 1 | U |
Problema 2 – Inversione
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.
| NASTRO INIZIALE | NASTRO FINALE |
| OOOH | HOOO |
|---|---|
| C | C |
| HCCOH | HOCCH |
| HOCCOCH | HCOCCOH |
| OOO | OOO |
Problema 3 – Completezza
Si scriva un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa sull’alfabeto {C, H, O}, 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.
| NASTRO INIZIALE | NASTRO FINALE |
| COO | NO |
|---|---|
| HCCO | SI |
| COCO | NO |
| HHHHH | NO |
| OHHHHC | SI |
Problema 4 – Ordinamento
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.
| NASTRO INIZIALE | NASTRO FINALE |
| CHOO | HOOC |
|---|---|
| COCCO | OOCC |
| HHHOOCCC | HHHOOCCC |
| COCHCOCH | HHOOCCCC |
| O | O |
Problema 5 – La chimica di Turing I
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).
| NASTRO INIZIALE | NASTRO FINALE | COMMENTO |
| CO2 | COO | Anidride carbonica |
|---|---|---|
| H2O2 | HHOO | Acqua ossigenata |
| CH4 | CHHHH | Metano |
| CH3CH3 | CHHHCHHH | Etano |
| CH2CH2 | CHHCHH | Etilene |
| O2 | OO | Ossigeno |
Problema 6 – La chimica di Turing II
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 perCOOCOOCOOCOO.
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.
| NASTRO INIZIALE | NASTRO FINALE |
| 4CO2 | COOCOOCOOCOO |
|---|---|
| CO2H | COOH |
| COOH | COOH |
| 3C2H2O | CCHHOCCHHOCCHHOCCHHO |
Problema 7 – Successione di Fibonacci
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 ntermini della successione di Fibonacci, separati esattamente da uno spazio.
| NASTRO INIZIALE | NASTRO FINALE |
| 5 | 1 1 2 3 5 |
|---|---|
| 8 | 1 1 2 3 5 8 13 21 |
| 10 | 1 1 2 3 5 8 13 21 34 55 |
| 1 | 1 |
Problema 8 – Successione di Collatz
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
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·10^18, ma manca una dimostrazione che ne garantisca la verità per qualunque x.
Sarete voi a trovarla?
| NASTRO INIZIALE | NASTRO FINALE |
| 5 | 5 16 8 4 2 1 |
|---|---|
| 6 | 6 3 10 5 16 8 4 2 1 |
| 13 | 13 40 20 10 5 16 8 4 2 1 |
| 27 | 27 82 41 124 62 31 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1 |
| 2 | 2 1 |
| 1 | 1 |
Problema 9 – La chimica di Turing III
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.
| NASTRO INIZIALE | NASTRO FINALE |
| 2H2O=O2H4 | SI |
|---|---|
| 2H2O+O2+2H=2O2+4H | SI |
| H2O+2OH=CH4 | NO |
| 4O=2O2 | SI |
| CH4+CO2+O2=2CO2+2H2O | NO |
Problema 10 – La chimica di Turing IV
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.
| NASTRO INIZIALE | NASTRO FINALE |
| 8CO2+8H2O | 4 |
|---|---|
| 6H2O+4CO2+COOH+4H2O | 5 |
| H2O+5CO2 | 0 |
| 6CH4 | 6 |
| 4O2+8H2O+4OH+4CO2+4C2H5 | 10 |