PARTE II. AUTOMI INFINITI. CALCOLABILITÀ — Cap. 5. La macchina di Turing
Come si è mostrato nell’Introduzione, la Teoria degli automi considera la nozione di automa come una formalizzazione della nozione di macchina di calcolo. Il modello degli automi finiti, presentato nella Parte I, può essere considerato come un modello generale della classe delle macchine con memoria finita, e può servire da termine di confronto con le macchine di calcolo reali, nella misura in cui ne influenza il funzionamento.
Da quanto mostrato nella Parte I, si è potuto vedere che il funzionamento degli automi finiti è caratterizzato dal fatto che ogni mossa dell’automa è completamente determinata dal suo stato interno e dal simbolo di ingresso letto in quel momento. In questo senso il funzionamento è rigido, l’automa non avendo iniziativa né creatività, e alla macchina mancando l’immaginazione e la fantasia proprie dell’uomo.
Si dice di un tale funzionamento che ha un carattere meccanico, e da qui deriva il termine “macchina”. Questo termine ha un carattere in qualche modo peggiorativo, poiché gli automi non sono mai considerati molto intelligenti, essendo l’uomo il termine di paragone.
Per definire più precisamente la nozione di funzionamento meccanico di una macchina reale, devono essere presi in considerazione due aspetti. Il primo è quello della memoria, che nel caso degli automi finiti si riduce a un numero finito di stati interni, cioè a una memoria finita. Il secondo aspetto è quello della rigidità delle regole di funzionamento, che nel caso degli automi finiti è massima.
Nel caso delle macchine reali, la memoria è di solito finita, ma può essere molto grande, e le regole di funzionamento possono essere più complesse. In teoria, per discutere la nozione di calcolabilità, è utile introdurre un modello idealizzato di macchina con memoria infinita, ma con regole di funzionamento completamente determinate. Questa è la macchina di Turing.
Nel seguito si farà spesso riferimento a un tipo molto noto di macchina reale: il calcolatore. Il calcolatore servirà come modello intuitivo e come punto di riferimento per le discussioni successive. È noto che il programma di un calcolatore non è altro che una descrizione del modo di elaborare i dati, in un linguaggio formale. Il programma descrive, in maniera precisa, i passi che devono essere eseguiti, nell’ordine stabilito dall’autore.
Il funzionamento del calcolatore riproduce, in un certo senso, il funzionamento della macchina astratta. La descrizione, in un linguaggio di programmazione, del modo di elaborare i dati è una descrizione completa, nel senso che in ogni momento si sa quale operazione debba essere eseguita successivamente. Perciò è naturale affermare che: ogni calcolo eseguito da un calcolatore può essere descritto con precisione.
Meno evidente è l’affermazione inversa: ogni procedura che possa essere descritta con precisione può essere programmata per essere realizzata da un calcolatore. Questa affermazione si basa sui lavori del matematico Alan Turing relativi alla calcolabilità.
In entrambe le affermazioni precedenti, la nozione di “descrizione precisa” è centrale. Turing propose una formalizzazione di questa nozione definendo una classe di macchine ideali capaci di eseguire qualsiasi procedura che possa essere descritta con precisione. Queste macchine furono chiamate macchine di Turing.
La descrizione di una procedura è un problema che ha preoccupato i ricercatori già prima della comparsa dei calcolatori.
Naturalmente, la nozione di descrizione presuppone un certo linguaggio.
Si può trovare un linguaggio per descrivere tutte le procedure? Esistono procedure che, nonostante una conoscenza perfetta, non possono essere descritte?
Tutte queste domande sono legate a una nozione molto importante: procedura effettiva o algoritmo.
