Turing l’uomo che risolveva problemi inventando macchine

Introduzione: Qual’e’ il piu’ semplice calcolatore che potete costruire e come potete usarlo per risolvere problemi concreti

Cose da fare: L’applet implementa una macchina di Turing. Un calcolatore che puo’ solo leggere e scrivere su un nastro infinito pieno di simboli seguendo un programma che gli dice per ogni simbolo letto cosa deve fare. La simulazione ha un certo numero di programmi precaricati.  Selezionate tra questi il Palindrome selector e cliccate su load new program. Vengono caricati programma e configurazione iniziale del nastro. Ora date Start . Osservate la macchina che  va avanti e indietro e alla fine da il suo responso scrivendo YES, La scritta iniziale e’ un palindromo (una sequenza di caratteri che, letta a rovescio, rimane identica. Ora provate a cambiare la stringa iniziale (sempre fatta da A e B) in modo che non sia un palindromo  , date Start e vedete cosa succede.

Cosa succede: Alan Turing  nacque esattamente 100 anni fa e invento’ la sua macchina quando ancora i computer non esistevano. La invento’ non per fare calcoli ma per risolvere dei problemi di logica matematica che si erano mostrati difficili da risolvere in altro modo. Senza saperlo aveva posto le basi dell’informatica diventandone uno dei pionieri assieme a Von Neumann che avrebbe in seguito inventato l’architettura di base del moderno computer. Come Neumann, Touring partecipo’ alla costruzione dei primi computer elettronici. Uno dei primi computer da lui costruiti servi’ per decifrare il codice della macchina Enigma dei tedeschi durante la seconda guerra mondiale. Anche qui ebbe l’intuizione fondamentale che solo una macchina poteva scoprire il codice prodotto da un’altra macchina.

La macchina di Turing e’  un computer ridotto ai suoi minimi termini. Nonostante  questo Turing dimostro’ che e’ in grado di fare una qualsiasi computazione. La programmazione del computer e’ fatta scrivendo una  serie di regole. La simulazione prevede la possibilita’ di scrivere nuovi programmi e voi potete provare ad esempio a scrivere un programma che somma due numeri binari. Il programma va scritto nella finestra programming. Esso prevede per ogni riga un’istruzione del tipo

[stato],[carattere],[nuovo stato],[nuovo carattere],[direzione(<>)]
Ad esempio il programma del palindromo comincia con:

1,_ 2,#,>
2,A 3,_,>
2,B 4,_,>
....

Cioe

1) All’inizio e’ allo stato 1 su una casella vuota : passa allo stato 2 scrivendo una “#” e andando a destra (>)

2) Ora e’ allo stato 2 su una “A” : passa allo stato 3 cancellando la A e andando a destra

3) Sempre nello stato 2 ma su una “B” : passa allo stato 4 , cancella la B e vai a destra

L’applet contiene istruzioni piu’ dettagliate sulla programmazione della macchina di Turing

 

Commenti:E’ possibile scaricare il codice sorgente cliccando su source code

Altri applet di concetti base e informatica

Il materiale ha come indirizzo http://ironphoenix.org/tril/tm/ .

Titolo in inglese: Turing machine simulator.

Author Suzanne Briton

Ricerca di pagine che hanno link a questo materiale .

Tweet

Leave a Reply

Your email address will not be published. Required fields are marked *