Problema 1 – Addizione unaria
Nei sistemi di numerazione posizionale, il valore denotato da un numero è ottenuto moltiplicando ogni cifra per la corrispondente potenza di una base.
Nel caso della notazione decimale, la base è 10; la cifra più a destra è moltiplicata per 100=1, quella successiva per 101=10, la terza da destra per 102=100, e così via.
Nella numerazione con base 1 (unaria), ciascuna cifra (si usa il carattere 1 per convenzione) viene moltiplicata per 1n=1, qualunque sia n.
Per esempio, 1210 = 1111111111111.
Si noti che lo 0 si esprime in unario con l’assenza completa del numero.
Si scriva un programma per Macchina di Turing che, ricevuta sul nastro una addizione unaria (composta da due numeri unari separati da +), lasci sul nastro il risultato dell’addizione, sempre espresso in unario.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| 11+111 | 11111 |
| 1111111+1 | 11111111 |
| 1+1 | 11 |
| 1+ | 1 |
| + |
Problema 2 – Addizione binaria
La notazione binaria è un sistema di numerazione posizionale con base 2.
In binario le cifre (0 o 1) vengono moltiplicate per 20=1, 21=2, 22=4, e così via, in base alla loro posizione.
Per esempio, 1210 = 11002.
Si scriva un programma per Macchina di Turing che, ricevuta sul nastro una addizione binaria (composta da due numeri binari separati da +), lasci sul nastro il risultato dell’addizione, sempre espresso in binario.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| 11+111 | 1010 |
| 1+1 | 10 |
| 0+0 | 0 |
| 10001+1101001 | 1111010 |
| 11011001101+1 | 11011001110 |
Problema 3 – Conversione romana
La notazione romana è un sistema di numerazione non-posizionale.
I romani lo adattarono dal sistema Etrusco, e la sua forma moderna si stabilizzò intorno al XIII secolo.
In questo sistema si usano alcune lettere per indicare determinati numeri; quando una lettera di valore minore segue una di valore maggiore, si intende che i due valori vadano sommati; quando invece una lettera di valore minore precede una di valore maggiore, si intende che il valore della prima vada sottratto da quello della seconda.
Le lettere usate generalmente sono:
- I=1
- V=5
- X=10
- L=50
- C=100
- D=500
- M=1000.
Per esprimere numeri maggiori venivano posti vari segni moltiplicatori sopra o accanto alle lettere usuali.
Si noti che i Romani non avevano un segno per lo 0, e che il sistema è ambiguo: per esempio, 99 si può scrivere sia IC che XCIX (entrambe le forme sono attestate in iscrizioni).
Noi adotteremo quest’ultima forma, in cui ogni cifra della rappresentazione decimale è codificata indipendentemente: 99 = 90 + 9 = XCIX.
Si scriva un programma per macchina di Turing che, ricevuto sul nastro un numero romano fra 1 e 3000, lasci sul nastro il corrispondente numero decimale.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| I | 1 |
| IV | 4 |
| IX | 9 |
| XIX | 19 |
| XCIX | 99 |
| DCLXVI | 666 |
| MCMXLV | 1945 |
| MMVI | 2006 |
Problema 4 – Addizione romana
Con riferimento alla notazione romana introdotta nell’esercizio precedente, si scriva un programma per macchina di Turing che, ricevuta sul nastro una addizione romana formata da due numeri romani compresi fra 1 e 10 separati dalla locuzione et (uno spazio,e, t, uno spazio), lasci sul nastro il risultato della loro addizione, sempre espresso in notazione romana.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| I ET I | II |
| III ET I | IV |
| IX ET X | XIX |
| IV ET IV | VIII |
| X ET V | XV |
Problema 5 – Conversione babilonese
Il sistema di numerazione babilonese, stabilizzatosi fra il 1900 e il 1800 a.C., era un sistema posizionale con base 60.
- La scelta di questa base rendeva semplici le divisioni per 2, 3, 5, 6, 10, 12, 15, 20 e 30 (tutti fattori di 60), nonché quelle per i loro prodotti (4, 6, 8, 18, 24, ecc.).
- D’altro canto, l’uso di una base 60 obbliga a usare 59 simboli diversi per rappresentare le cifre (più lo spazio, che rappresentava lo 0).
- Fortunatamente, i Babilonesi usavano il sistema cuneiforme, e il simbolo di ciascuna cifra era ottenuto incidendo sulle tavolette un certo numero di simboli < (che indicavano le decine) e Y (che indicavano le unità).
- Per esempio, la cifra 43 era rappresentata dal simbolo 43 nella tabella accanto, e che noi indicheremo con <<<< YYY.
- Naturalmente, se tale simbolo compariva nella posizione più a destra di un numero il suo valore era moltiplicato per 600=1; in quella successiva era moltiplicato per 60, poi per 3600, ecc.
- Noi rappresenteremo le cifre babilonesi separandole con un ., e usando il simbolo = al posto dello spazio per denotare lo 0.
Si scriva un programma che, ricevuto sul nastro in ingresso un numero in notazione babilonese, lasci sul nastro in uscita il corrispondente numero in notazione decimale.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| YYYY | 4 |
| < | 10 |
| <<<YY | 32 |
| Y.<YYY | 83 |
| <.=.YY | 36002 |
| <<<YYY.<<YYYYYY | 2006 |
| <.= | 600 |
Problema 6 – Sequenza di pari
Si scriva il programma di una Macchina di Turing che, dato un numero sul nastro, stampi la sequenza dei numeri pari compresi fra 0 e il numero dato, separati da “.”.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| 5 | 0.2.4 |
| 0 | 0 |
| 2 | 0.2 |
| 17 | 0.2.4.6.8.10.12.14.16 |
Problema 7 – Densità di una sequenza
Si scriva il programma di una macchina di Turing che, data una sequenza di numeri sul nastro, separati da ‘.’ e compresi tra 0 e 20, lasci sul nastro S se questa contiene almeno 10 numeri distinti, N altrimenti.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| 0.2.5.6.7.8.10.11.19.11.13 | S |
| 0.0.1.5.1.0.11.10.20.20.20 | N |
| 10 | N |
| 0.0.1.2.3.4.5.6.7.8.9 | S |
Problema 8 – Verso di una sequenza
Una sequenza di interi n1…nk (con k≥2) è detta
- crescente se ciascuno degli interi successivi al primo è maggiore del precedente (ovvero, ∀i>1, ni>ni-1);
- decrescente se ciascuno degli interi successivi al primo è minore del precedente (ovvero, ∀i>1, ni<ni-1),
- incerta in tutti gli altri casi.
Si scriva il programma di una macchina di Turing che, data una sequenza di numeri sul nastro, separati da ‘.’, lasci sul nastro C se la sequenza è crescente, D se è decrescente, I se è incerta.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| 0.2.4.5 | C |
| 10.15.23.20.6 | I |
| 10.5 | D |
| 25.20.3.3.0 | I |
Problema 9 – Numeri perfetti
Un numero si dice perfetto se la somma dei suoi divisori propri ha come risultato il numero stesso.
Sono perfetti
- 6 (1+2+3=6)
- 28 (1+2+4+7+14=28)
- 496
- …
Si scriva un programma per la macchina di Turing che, dati sul nastro un numero e la lista dei suoi divisori, lasci sul nastro P se il numero è perfetto, N altrimenti.
Si assuma che il nastro inizialmente sia della forma N?D+D+D…, dove N è il numero e i D sono i suoi divisori.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| 6?1+2+3 | P |
| 7?1 | N |
| 15?1+3+5 | N |
| 28?1+2+4+7+14 | P |
| 30?1+2+3+5+6+10+15 | N |
Problema 10 – Numeri di Padovan
I numeri di Padovan sono definiti dalla seguente formula per ricorrenza:
- P(n)=1, per n=1,2,3
- P(n)=P(n-2)+P(n-3), per n>3
I primi numeri di Padovan sono dunque, nell’ordine, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, …
Si scriva un programma per Macchina di Turing che, ricevuto sul nastro in ingresso un intero n, lasci sul nastro in uscita l’n-esimo numero di Padovan P(n).
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| 1 | 1 |
| 8 | 5 |
| 14 | 28 |
| 27 | 1081 |
| 44 | 128801 |