Macchina di Turing

Programmazione, algoritmica, teoria dell'informazione, ...
Rispondi
Avatar utente
urano88
Messaggi: 39
Iscritto il: 08 mag 2006, 19:16
Località: Brescia/Padova

Macchina di Turing

Messaggio da urano88 »

Mi sono appassionato da un po' di tempo alla programmazione della Macchina di Turing risolvendo diversi problemi anche in vista della gara di programmazione del 2007 (unipi)
A questo link c'è tutto il materiale necessario per iniziare a programmare la Macchina di Turing compresi: mini-manuale introduttivo, simulatore e quesiti delle precedenti edizioni
http://www.di.unipi.it/settcult/?loadpa ... ighlight=3
Se qualcuno mi vuole contattare per un'eventuale ricerca congiunta di soluzioni ai problemi sono disponibile.


Lascio questo quesito (di mia invenzione) per chi già la conosce

conversione decimale/unario
Scrivere un programma per Macchina di Turing che, ricevuto sul nastro un numero intero N (arbitrariamente grande) in notazione decimale, vi lasci la sua corrispondente rappresentazione unaria ovvero una sequenza di N simboli uguali.
nota -> lo zero in unario è rappresentato con la totale assenza del simbolo.

Non so se è risolvibile, ma credo di sì, io non ci sono ancora riuscito se non limitando N.
MindFlyer

Re: Macchina di Turing

Messaggio da MindFlyer »

urano88 ha scritto:Non so se è risolvibile, ma credo di sì, io non ci sono ancora riuscito se non limitando N.
Certo che è risolvibile: le macchine di Turing sono uno dei modi (equivalenti) per definire le funzioni calcolabili, e questo significa che ogni algoritmo scrivibile in qualunque linguaggio di programmazione è anche scrivibile con una macchina di Turing.
Avatar utente
phi
Moderatore
Messaggi: 350
Iscritto il: 01 gen 1970, 01:00
Località: Bath, UK
Contatta:

Messaggio da phi »

Ciao!
Io ho partecipato alla gara delle macchine di Turing in prima (nel 2002) e quest'anno. E' carina come esperienza. :) Tra l'altro ci sono diverse aggiunte alla notazione (le avrai viste, immagino) che quest'anno ci sono state annunciate appena prima della gara... (e andavano usate nei problemi!)
Io di soluzioni ne ho un bel po', se hai bisogno di qualcosa puoi chiedere (credo di aver conservato quasi tutte quelle che ho scritto). So anche che gli organizzatori hanno in programma di stampare un libriccino con le sol di tutti i problemi proposti nelle precedenti edizioni, potrebbe essere pronto per l'anno prossimo...
Quanto al problema che proponi è semplice anche se un po' "noioso", nel senso che i tempi di esecuzione sono necessariamente lughi...

Potresti risolverlo con qualcosa del genere (scrivendo "a" come "simbolo" nella tua notazione unitaria):

(0,[1..9],1,[0..8],>)
(1,a,1,a,>)
(1,-,2,a,<)
(2,a,2,a,<)
(2,[0..9],0,[0..9],-)
(0,0,0,9,<)
(1,[0..9],1,[0..9],>)
(0,-,3,-,>)
(3,9,3,-,>)

Il simulatore java non funziona sul mio computer quindi non ho controllato e potrebbe esserci qualche errore, fammi sapere tu, ma il principio è quello.
Avatar utente
urano88
Messaggi: 39
Iscritto il: 08 mag 2006, 19:16
Località: Brescia/Padova

Messaggio da urano88 »

Il tuo programma funziona solo per i numeri con una sola cifra. Il problema sta nel definire il giusto peso in base alla posizione della cifra (c*10^0, c*10^1, c*10^2,...) e aggiungere di conseguenza il corretto numero di simboli, ma potendoci essere infinite cifre e quindi infinite posizioni, avrei bisogno di un numero infinito di stati (che non ho) per identificare la posizione.

Per rendere più comprensibili i programmi è possibile dare dei nomi agli stati (almeno con il simulatore in java) invece di numerarli progressivamente.

Di simulatori sparsi in rete ce ne sono un sacco, prova a guardare qui:
http://www.google.it/search?hl=it&q=Tur ... erca&meta=

Per quanto riguarda la mia attività, ad oggi il problema più complesso che ho risolto è la conversione romano/decimale. Ora sto lavorando sulla conversione babilonese/decimale (problema n° 5, anno 2006) ma anche qui si presenta il problema sopracitato: infatti non limitando il numero di cifre iniziali ho bisogno di un infinito numero di stati per identificare le posizioni o quantomeno di una struttura dinamica che sia in grado di generare il numero di stati che mi servono in funzione del numero di cifre iniziali...
MindFlyer

Messaggio da MindFlyer »

urano88 ha scritto:potendoci essere infinite cifre e quindi infinite posizioni, avrei bisogno di un numero infinito di stati (che non ho) per identificare la posizione.
Per sostenere un'affermazione del genere dovresti almeno dimostrarla, cosa che non puoi fare perché è falsa. Ma l'hai letto il mio post precedente??
Non hai bisogno di avere uno stato per ogni cifra, basta decrementare il numero in input un'unità alla volta, facendo attenzione al "riporto" e salendo su di una posizione ogni volta che ti ritrovi a decrementare uno 0. Per questo ti bastano 4 stati, e volendo anche di meno.
Il programma di phi fa proprio questo, e se solo avessi la voglia di leggerlo per bene te ne accorgeresti da solo. Ti faccio presente che phi quest'anno ha vinto il 3° premio a livello nazionale, perciò è anche nel tuo interesse riservare un po' più di attenzione a quello che scrive sull'argomento.
Il fatto è che il programma di phi assume che la testina all'inizio della computazione si trovi sull'ultimo carattere dell'input, e non sul primo, come forse vuole il simulatore che hai usato. In questo caso ti basta aggiungere uno stato iniziale che manda la testina a destra fino al primo carattere uguale a "-", dopodiché torna a sinistra di 1 e riparte come al solito. Alternativamente, inverti tutti i "<" e ">" e scrivi le cifre dell'input in ordine inverso! :wink:
Avatar utente
urano88
Messaggi: 39
Iscritto il: 08 mag 2006, 19:16
Località: Brescia/Padova

Messaggio da urano88 »

Il tuo post precedente è irrilevante, quello che hai scritto lo sapevo benissimo anch'io e io non ho chiesto se quel problema fosse risolvibile, bensì come fosse risolvibile.

Ho scritto che il programma di Phi non funziona perchè l'ho provato in un simulatore (quello ufficiale) e non funziona, se ad esempio scrivo 10 sul nastro iniziale il programma restituisce una sola A il che significa che non considera la posizione del 1 che è davanti ad un altra cifra e quindi vale 10 A. Anche scrivendo l'input invertito, in questo caso 01, il risultato è errato: sul nastro resta un 1 con la macchina fissa sullo stato 3: siamo ben lontani dalle 10 A.
Riprendendo in mano il testo del mio problema, un numero intero N in notazione decimale significa che se N ha M cifre la prima cifra a destra di N varrà c*10^0, la seconda varrà c*10^1, la terza c*10^2... fino alla prima a sinistra che vale c*10^(M-1) dove c indica la cifra che sto considerando. Quindi ho bisogno di diversi stati che mi consentono di capire se sto considerando la prima cifra, la seconda, la terza o la Mesima per potere di conseguenza aggiungere c, c*10, c*100 o c*10^(M-1) simboli ogni volta che decremento c. Ma potendo essere M infinitamente grande, ho bisogno di infiniti stati o meglio, dato che M sarà sempre un numero finito, ho bisogno di una struttura dinamica che cresce in funzione di M, o forse no?

Comunque il simulatore ufficiale si posiziona sul primo carattere a sinistra.
MindFlyer

Messaggio da MindFlyer »

Rileggi il mio post, urano.
Oltre ad invertire l'ordine dei caratteri dell'input, devi invertire anche i simboli "<" e ">" nel programma, altrimenti grazie al piffero che non funziona!
Inoltre continui a sbagliare sul fatto di avere bisogno di uno stato per ogni cifra, come ho già avuto modo di farti notare!! Se dici una cosa del genere la devi dimostrare, o altrimenti rilassati e dai un'occhiata a come funziona il programma di phi.
Avatar utente
phi
Moderatore
Messaggi: 350
Iscritto il: 01 gen 1970, 01:00
Località: Bath, UK
Contatta:

Messaggio da phi »

Provo a spiegare un po' "a parole" cosa dovrebbe fare l'algoritmo, visto che forse non ci siamo intesi proprio sul metodo...
Poi il codice, una volta che si capisce l'idea, è secondario.

Passo 0. Scorro l'input fino in fondo. Questo non l'ho fatto, quindi solo per una cifra il tutto funziona...

Passo 1. Sottraggo 1 al numero.

Passo 2. Scrivo una a in fondo all'output.

Riprendo dal passo 1 finché il numero di partenza non diventa 00...00. Allora cancello le cifre inutili e lascio solo le a.

Spero sia chiaro che questo metodo funziona, e non ha bisogno di infiniti stati. Ora però, metterlo in pratica è un pochetto contorto.
In particolare, il passo 1 funzionerà così:
- se l'ultima cifra è maggiore di 0, sottraggo 1 e ho fatto;
- se è 0 scrivo 9, vado indietro e ricomincio il procedimento;
insomma, vado indietro finché non trovo una cifra >0; se non la trovo basta, ho finito, cancello i 9 che ho scritto.

Il nastro dovrebbe evolvere in questo modo:

Esempio, input 11
11
10a
19a
09aa
08aaa
...
01aaaaaaaaaa
00aaaaaaaaaaa
09aaaaaaaaaaa
99aaaaaaaaaaa
9aaaaaaaaaaa
aaaaaaaaaaa

Ripeto, se vuoi cambio il codice. Dimmi tu. Poi sai, ce ne sono tanti di simulatori, ma sono perlopiù scomodi e lenti da usare...
Avatar utente
urano88
Messaggi: 39
Iscritto il: 08 mag 2006, 19:16
Località: Brescia/Padova

Messaggio da urano88 »

Va bene, va bene, quando ho scambiato l'ordine dei <e> tutto si è meso a posto e ho capito al volo, ragionavo nel modo sbagliato...

Quello della conversione babilonese l'hai già fatto? nel caso in cui mi servisse una spinta...
Avatar utente
stefano88
Messaggi: 111
Iscritto il: 01 gen 1970, 01:00
Località: Latina
Contatta:

Messaggio da stefano88 »

La conversione babilonese sono l'unico che l'ha fatta quest'anno.
Se recupero il testo e/o il foglio di brutta della gara ti posso dare l'algoritmo a grandi linee.

Intanto ecco il testo
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.

Fammi provare la soluzione (oscurata nel caso ti servisse solo qualche hint)

Se avessi uno scanner farei prima a mandarti l'algoritmo su carta che è la versione quasi definitiva di quello che poi abbiamo consegnato alla gara.
Provo a spiegarlo più a parole che a cinquine di Turing. Poi se servià approfondirlo magari scriverò qualche pezzo in turingese (o come cavolo si chiama quella stramberia :D ). Esempio di input: YY.<<Y.=
Allora all'inizio scrivo una X all'inizio e alla fine del nastro per delimitare il numero e facilitarmi il lavoro. Per cui avrò XYY.<<Y.=X.
Poi riavvolgo il nastro e mi posiziono al primo carattere non nullo dopo la X iniziale.
Se leggo una Y vuol dire che la cancello e devo incrementare di 1 il numero in decimale che tengo alla sinistra della prima X, il che è relativamente facile, basta solo stare attenti ai riporti se si trova un 9. Dopodichè si ritorna a leggere il primo carattere non nullo dopo la X.
Quindi dopo questo passaggio si ha il nastro 1X-Y.<<Y.=X; Ripetiamo per la seconda Y: 2X--.<<Y.=X
Ora si arriva al passaggio cruciale: il passaggio in base 60. Ma per fare ciò bastava moltiplicare per 60 il numero finora ottenuto.
Cioè, se per esempio ho 5A1 in esadecimale lo posso scrivere in decimale come 5*16^2 + 10*16 + 1. Quindi un'ipotetica conversione da hex a dec consisterebbe nel convertire 5 in decimale (5), moltiplicarlo per la base 16, sommare A in deciamle (10), moltiplicare il tutto per 16, sommare 1. Infatti ne uscirebbe (5*16 + 10) * 16 + 1 che è uguale alla notazione classica per somma di potenze.
Ora, forse ho scritto da cane ma il passaggio chiave è questo e in base 60 funziona uguale. Prendo la prima cifra, YY, la converto in decimale e moltiplico per 60. Poi aggiungo la seconda cifra convertita e rimoltiplico, così fino all'ultima cifra.
Per cui se leggo un . devo effettuare la moltiplicazione per 60 dle numero, che è la parte più rognosa. Io ho fatto tutti gli stati di tutti i riporti della molt. per 6 poi ho scalato di una cifra per moltiplicare per 10.
Se invece si legge un < si aggiunge 10, che è come aggiungere 1 ma con l'accortezza di saltare una cifra.
Se si legge una X vuol dire che abbiamo letto tutti i caratteri, si cancellano le 2 X e il nastro conterrà il risultato finale.
Dei = ce ne freghiamo altamente, comunque avevo messo pure un controllo nel caso la soluzione fosse 0.
Questo era il problema che dava più punti però non era il più difficile credo.
Rispondi