30 marzo 2008  6

La macchina di Turing

Foto di Alan Turing La definizione di macchina formale di Turing è una delle teorie più affascinanti tra quelle che hanno posto le basi per l'evoluzione dell'informatica moderna e dei concetti legati alla struttura di un programma e degli algoritmi ad essi collegati. Sviluppata da Alan TuringW, questa macchina puramente teorica è nata come sussidio allo studio degli algoritmi e della possibilità di risolvere alcuni particolari problemi di elaborazione.

In altre parole si tratta di un "banco di prova" teorico per verificare se un problema è risolvibile mediante computer.

Due parole su Turing

Alan TuringW può essere considerato a tutti gli effetti uno dei dei più grandi matematici della storia: durante la seconda guerra mondiale si occupò massicciamente di codici, cifrari e decrittazione e creò il ColossusW, lontano antesignano del computer moderno, con cui riusciva a decifrare i codice tedeschi creati con la famosa macchina Enigma. Turing fù anche il primo a gettare le basi per tutti i successivi studi sull'inteliggenza artificiale (Test di TuringW).

Morì suicida a 42 anni ingerendo una mela avvelenata con cianuro di potassio (si disse poichè era ossessionato dalla favola di Biancaneve fin da fanciullo), isolato ed inviso da tutti per la sua dichiarata omosessualità che gli valse anche la condanna alla castrazione chimica.

Alcuni sostengono che il simbolo della mela morsicata utilizzato poi più di venti anni dopo dalla AppleW come logo aziendale, sia stato scelto proprio in onore del famoso matematico londinese.

La macchina

Cercherò di descrivere nella maniera più semplice possibile la teoria (a dire il vero anche abbastanza corposa se si volesse approfondire l'argomento) che Turing elaborò per la definizione della sua macchina formale.

Egli decise che questo apparato doveva possedere tre caratteristiche principali: un sistema di memorizzazione esterno dei dati immessi e di quelli elaborati, un dispositivo di lettura e di scrittura di tali dati ed un meccanismo di controllo per stabilire le azioni da intraprendere.

L'unità esterna di memorizzazione della macchina di Turing è definita come un "nastro" (paragonabile proprio ad un nastro magnetico, se vogliamo) di lunghezza infinita: esso è in grado di memorizzare tutti i dati relativi ad ogni particolare elaborazione indipendentemente dalla loro quantità. Il nastro è sezionabile in celle (o locazioni di memoria): ciascuna di esse può contenere un simbolo o essere vuota (null). Il dispositivo di lettura e scrittura, al pari del supporto di memorizzazione, può essere assimilato ad una testina magnetica in grado di trasferire i simboli desiderati sul nastro stesso e, al contempo, avente la possibilità di deciderne la direzione di movimento mediante una unità di controllo. Quest'ultima inoltre contiene naturalmente il programma da eseguire.

macch_turing

In quest'ottica, la macchina risulta sostanzialmente "dedicata" ad ogni unica applicazione che si intende simulare: infatti essa non è dotata di un dispositivo di memoria di massa sul quale far risiedere o poter leggere il programma stesso.

La logica di controllo della macchina è composta da frasi o stringhe composte da cinque campi o istruzioni (dette "quintette"). L'esecuzione di ogni quintetta è vincolata sostanzialmente sia dal simbolo presente al momento nell'unità di lettura e scrittura che dallo stato della macchina. Lo stato della macchina è una condizione essenzialmente arbitraria. In linea di principio potremo definire uno stato arbitrario Si di avvio, nel quale la macchina inizia l'esecuzione della procedura di calcolo, fino a raggiungere la speciale condizione H (Halt) che corrisponde al termine dell'esecuzione. Tra questi due stati possono naturalmente esserci n stati differenti che riflettono appunto il risultato dell'elaborazione in corso e stabiliscono quale quintetta eseguire di conseguenza.

Ogni quintetta è composta dai seguenti cinque elementi:

  1. L'attuale stato della macchina
  2. Il simbolo contenuto nella cella correntemente in corso di lettura
  3. Il simbolo da scrivere nella medesima cella se non avviene alcun modifica del dato
  4. Lo stato della macchina a seguito delle precedenti operazioni (2 e 3)
  5. La direzione di scorrimento del nastro (avanti o indietro)

Ad esempio, la quintetta (S1, 7, 9, S2, R) viene eseguita ogni qualvolta la macchina si trova nello stato S1 e la testina di lettura legge un 7. A quel punto, il 7 viene sostituito da un 9, la macchina viene posta nello stato S2 ed il nastro viene fatto scorrere di una posizione verso destra (R = right = destra).

Con queste premesse, la progettazione di una macchina di Turing per la soluzione di un determinato problema significa definire il formato dei dati immessi mediante il sistema di lettura, quello dei dati prodotti durante l'elaborazione e che poi, di conseguenza, verranno riprodotti sul nastro magnetico quando ad elaborazione terminata si raggiungerà lo stato H, e, infine, il numero di quintette necessarie per l'implementazione dell'intero algoritmo.

Giusto a titolo di esempio, per definire l'istruzione logica AND con una macchina di Turing sarebbe necessario un insieme (quindi un programma) di 10 (dieci) quintette per poter consentire tutte le possibili combinazioni dell'operatore in questione, tenendo presente che, per ciascuna operazione possibile il numero di quintette utilizzato sarebbe sicuramente inferiore (l'equazione 1 AND 1 = 1, sfrutta infatti solo 5 stringhe).

(N.B.: tutte le immagini ivi riprodotte sono copyright dei rispettivi autori)

Esprimi il tuo giudizio

Commenti (6) -

Daniele
Daniele
30 mar 2008 alle 20:27  01
Un altra pietra fondamentale e molto interessante dell'informatica è l'architettura di Von Neumann. Questa macchina di Turing mi ricorda molto il prof. di sistemi Smile
annarita
annarita
30 mar 2008 alle 20:36  02
Bellissimo questo post, Cristiano, sia sotto l'aspetto storico che per i riferimenti matematici! Ti dispiace se lo cito su Matem@ticaMente? E' utilissimo per i mei ragazzi.

Ti ho appena votato su OKNO!

Bacioni
Cristiano
Cristiano
30 mar 2008 alle 22:11  03
@ Daniele:
Verissimo! Infatti ho intenzione di parlare diffusamente di Von Neumann (matematico d'eccezione anche lui morto prematuramente) in uno dei prossimi articoli dedicati alla storia dell'informatica.

@ annarita:
Assolutamente! Ti ringrazio per la preferenza, come sempre Wink
Danilo
Danilo
30 mar 2008 alle 22:31  04
Grazie Cristiano per il bel post, non conoscevo affatto l'argomento.
Traffyk
Traffyk
03 apr 2008 alle 13:14  05
Che palle devo fare l'esameeeeee, Cristià non ti ci mettere pure tuu Laughing hihih
Va&Sa
Va&Sa
13 ott 2008 alle 11:16  06
noooo abbiamo l'interrogazione!!!!!!!!!!

Aggiungi Commento

biucitecode
  • Commento
  • Anteprima
Loading


| |   |  

Codice QR

Codice QR - cristianofino.net

Ultimi Commenti