Home > Intelligenza Artificiale. Da Leibniz ai robots > L’ IMITAZIONE DEL PENSIERO: La macchina di Turing

L’ IMITAZIONE DEL PENSIERO: La macchina di Turing

novembre 21, 2009

Alan M. Turing nel suo tentativo del 1936 di rispondere al problema della decisione di Hilbert (conosciuto meglio come Entscheidungsproblem) inventò un calcolatore ideale, chiamato da allora Macchina di Turing, nell’articolo On Computable Numbers, with an Application to the Entscheidungsproblem.1

La MT utilizza come supporto fisico per le operazioni di calcolo un nastro,2 o meglio l’astrazione di un nastro, infatti questo è monodimensionale, biinfinito (si può scorrere avanti e indietro infinitamente) ed è diviso in celle, le quali possono ospitare solo un simbolo dell’alfabeto alla volta.

I simboli dell’alfabeto di MT sono finiti (Σ={ s1, s2, …, sn }) e si indica con s0 la cella vuota.3

Per la lettura e scrittura dei simboli sul nastro la MT utilizza una testina mobile che “osserva” una cella alla volta. I movimenti della testina sul nastro sono tre: spostamento a destra, a sinistra e posizionamento al centro (utilizzato per la configurazione finale); mentre le operazioni che può compiere su ogni singola cella sono due: lettura e scrittura. La cancellazione della cella in realtà è la sovrascrizione del simbolo s0 sul simbolo già presente sul nastro.

L’elemento non meccanico della MT è lo stato interno. Lo stato interno di una MT è paragonabile allo stato mentale dell’uomo durante una procedura di calcolo, e dipende dalle operazioni precedenti.

La MT può assumere uno stato interno q0, q1, …, qn (uno e solo uno alla volta); il numero dei possibili stati interni è finito.

La combinazione tra lo stato interno e il simbolo in lettura della testina in quel dato momento viene detta configurazione di una MT.

La MT può eseguire quindi tre operazioni atomiche: la sostituzione di un simbolo con un altro simbolo; spostamento della testina su una delle celle immediatamente adiacenti (la prima a destra o la prima a sinistra) e il cambiamento dello stato interno della macchina.

La rappresentazione grafica di un operazione atomica è per esempio “s1 D q2”, leggo il simbolo s1 la testina si sposta a destra e si passa allo stato interno q2.

Le istruzioni che una MT può eseguire sono rappresentabili secondo una quintupla formata dalla configurazione e seguita dall’operazione che la macchina deve svolgere quando si trova in quella determinata configurazione.

L’insieme di istruzioni formano una tavola della MT; è necessario che non ci sia la possibilità che ad una determinata configurazione corrisponda più di un’operazione da eseguire.

Il calcolo si ferma quando arrivati ad una determinata configurazione non segue alcun’altra operazione e si arriva alla configurazione finale con la testina che si sposta al centro e la MT ha come stato interno q0 (questo stato interno non è indispensabile, si potrebbe costruire una macchina che non termini).

L’input è già impresso sul nastro all’avvio della MT, mentre l’output è quello che rimane sul nastro al termine della tavola di istruzioni.

Per convenzione la testina della MT è posizionata all’avvio sulla prima cella a sinistra con un simbolo e ha come stato interno q1.

Ogni tavola può essere rappresentata da un numero descrittivo, ottenuto con una codificazione simile alla codifica di Gödel. Se la macchina universale di Turing dovesse computare il proprio numero descrittivo si troverebbe in una condizione non soddisfacente.4

1 Turing Alan M., On Computable Numbers, with an Application to the Entscheidungsproblem, «Proceedings of the London Matematical Society» (2), vol. 42, 230-65 (1937);

2Questo tipo di supporto di immagazzinamento dati non è dei migliori dal punto di vista delle prestazioni. Turing si accorse che il nastro, come ogni altro tipo di supporto sequenziale (i dispositivi di memorizzazione sequenziale sono tutti quei dispositivi la cui lettura deve partire dall’inizio e arrivare fino al punto desiderato un passo alla volta) erano troppo lenti, e sarebbe stato meglio sostituirlo con un dispositivo di memorizzazione diretto (la lettura di una determinata area è possibile direttamente spostando la testina su quell’area)

3L’alfabeto finito usato nella Macchina di Turing, è binario, i simboli sono “cella piena” e “cella vuota”.

4Tra le MT distinguiamo quelle bloccate da quelle senza blocco. Le prime sono macchine che terminano le loro operazioni, mentre le seconde continuano per un tempo indefinito. Un classico esempio di MT senza blocco è quella di una macchina che deve calcolare la successione di cifre decimali di un numero irrazionale come π, perché appunto continuano a calcolare all’infinito senza mai arrestarsi. Le macchine bloccate invece sono MT che terminano le loro operazioni. Turing chiama soddisfacenti quei numeri descrittivi corrispondenti alle macchine senza blocco, viceversa sono per lui insoddisfacenti i numeri corrispondenti a macchine bloccate.

%d blogger cliccano Mi Piace per questo: