X edizione

Addizione unaria7

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.

Addizione binaria10

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.

Conversione romana28

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 = XC IX. 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.

Addizione romana20

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.

Conversione babilonese35

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

Sequenza di pari10

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 “.”.

Densità di una sequenza15

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.

Verso di una sequenza18

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, niincerta 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.

Numeri perfetti22

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, ecc. 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.

Numeri di Padovan30

I numeri di Padovan sono definiti dalla seguente formula per ricorrenza:
P(n)=P(n-2)+P(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).