Contenuti

In tutti gli algoritmi, siano essi eseguiti a carta e penna o con l’ausilio di un sistema di calcolo, possono essere individuate alcune caratteristiche comuni: un algoritmo è di lunghezza finita, esiste un agente di calcolo che esegue le istruzioni che compongono l’algoritmo, l’agente di calcolo ha a disposizione una memoria illimitata per i risultati intermedi del calcolo, il calcolo avviene per passi discreti, il calcolo non è probabilistico.

Nella pubblicazione “On computable Number, with an application to the Entscheidungsproblem” (1936), Alan Turing descrisse formalmente un sistema di calcolo in grado di eseguire un generico algoritmo con le precedenti caratteristiche.
La sua Macchina è costituita da un automa a stati finiti deterministico ovvero da un insieme finito di stati {q1, …, qn} e da una funzione di transizione. Un altro elemento fondamentale è il nastro formato da una serie infinita di celle unitarie costituendo così la memoria della macchina. Infine, una testina mobile sul nastro è in grado di leggere e scrivere un carattere alla volta scelto nell’alfabeto di simboli $, 0 e 1. Un algoritmo per tale macchina è un insieme finito di istruzioni nella forma (q, r, q’, w, m): se la Macchina è nello stato q e legge il simbolo r, transita nello stato q’ scrivendo nella cella corrente il simbolo w e muovendo la testina di una cella in direzione m.

I problemi risolvibili con una qualsiasi architettura più complessa, con più nastri, più stati o con un alfabeto più ricco sono gli stessi risolvibili dalla Macchina appena descritta e per di più sono risolvibili nella medesima classe di complessità. In questo senso, i calcolatori costruiti con le diverse tecnologie che hanno segnato il XX secolo sono tutti riconducibili allo stesso modello. L’evoluzione tecnologica sta quindi lavorando nella velocità di computazione, nella dimensione della memoria disponibile, nella miniaturizzazione, nei consumi e nei costi, ma in linea teorica, ciò che possiamo fare oggi con un moderno processore multicore poteva essere fatto da un ricco e paziente signore con un calcolatore a valvole degli anni 40′ come lo Zuse Z3 essendo entrambe le architetture Turing complete.

Negli stessi anni sono stati proposti altri modelli in grado di descrivere la calcolabilità come il lambda-calcolo e le funzioni parziali ricorsive ma puntualmente è stata dimostrata l’equivalenza con il modello proposto da Turing portando alla formulazione della tesi di Church-Turing (1936): “la classe delle funzioni intuitivamente calcolabili coincide con la classe delle funzioni Turing calcolabili”.

Grazie al lavoro pionieristico di Alan Turing, l’Informatica oggi è considerata una scienza poichè esiste un modello universale che ne descrive le potenzialità e i limiti.