Turing, Alan Mathison

matematico e logico inglese (Londra 1912 - Wilmslow 1954). Docente al King's College di Londra, fu a Princeton dal 1936 al 1938, dove collaborò con A. Church. Nel dopoguerra lavorò a Manchester alla costruzione di calcolatori. Noto soprattutto per le sue ricerche di logica e teoria degli automi, ha lasciato vari contributi di matematica e nello studio della cosiddetta intelligenza artificiale. Il suo maggior apporto resta però quello dato alla teoria della computabilità e al problema della decisione che affrontò in modo originale, nel 1936, attraverso la “macchina” teorica che porta il suo nome.

Il problema affrontato originariamente da Turing consisteva nel definire in modo del tutto generale una macchina calcolatrice; Turing la definì formalmente come una scatola nera con un numero finito di stati: un cambiamento di stato implica un'interazione della macchina con l'ambiente esterno. L'interazione fu schematizzata da Turing nel modo seguente: il mondo esterno è per la macchina un lungo nastro di carta suddiviso in tanti quadrati aventi come lato la larghezza stessa del nastro; su ogni quadrato può essere impresso un segno oppure no. In altri termini, si può dire che vi può essere segnato uno oppure zero. La macchina osserva il nastro, un quadrato per volta, e lo può spostare, sempre di un passo per volta, in avanti o indietro. In dipendenza di ciò che legge essa può modificare il proprio stato. Inoltre, essa può modificare il segno che legge nel nastro oppure può lasciarlo com'è. Una macchina siffatta può scrivere (ovvero formare) una successione infinita di cifre 0,1; in altri termini, può formare una qualsiasi successione di numeri reali. Basta, a questo fine, che in un tratto finito di nastro sia data opportuna istruzione alla macchina stessa. La macchina di Turing è una macchina universale, nel senso che essa è in grado di elaborare una qualsiasi successione di segni scritti nel nastro prodotto da una qualsiasi altra macchina. Per quanto a priori non si potesse dire che ciò fosse possibile (una macchina di Turing è infatti in grado di fare lo stesso lavoro di una macchina, per esempio, 10 volte più grande, o 100 volte più complessa), Turing dimostrò matematicamente la possibilità della sua costruzione, mostrando come, con un numero finito di simboli, fosse possibile dare una descrizione del tutto generale di una qualsiasi macchina. Tale descrizione è costituita da un nastro contenente anche dei tratti vuoti il cui riempimento dà luogo a una macchina specifica tra le infinite possibili. La macchina di Turing, per poter assolvere la funzione di una macchina specifica, deve pertanto essere fornita della descrizione di una tale macchina e deve essere in possesso delle stesse istruzioni necessarie alla macchina specifica per poter operare. Non ci sono difficoltà di ordine teorico a estendere la definizione di Turing a una macchina universale che non produca pezzi di carta, ma altre macchine; non ci sono neanche difficoltà a concepire macchine che si autoriproducano; basta introdurre la macchina in un ambiente in cui abbondino gli elementi necessari per la costruzione. Poiché gli automi prodotti possono essere identici all'originale, essi hanno necessariamente la capacità di autoriprodursi a loro volta. Poiché il programma di autoriproduzione ha le stesse funzioni del materiale genetico delle cellule viventi, appare chiaro come sia possibile introdurre nel programma delle “mutazioni” casuali che portino ad automi diversi da quello originario.