L'antenato del computer

[11/11/2004] La macchina di Turing

La nascita dell'idea di computer è dovuta al matematico inglese Alan M. Turing che nel 1936 progettò una macchina la quale, anche se si tratta di un concetto matematico astratto e non di un oggetto fisico, rappresenta un primitivo e primordiale "prototipo" del computer moderno.

L'intuizione di Turing fu quella di "spezzare" l'istruzione da fornire alla macchina in una serie di istruzioni più semplici: un processo analogo a quello utilizzato dai programmatori odierni.

Descrizione della Macchina di Turing

Una macchina di Turing è costituita da due elementi.

Un nastro di lunghezza infinita, suddiviso in celle, in ognuna delle quali può essere scritto un simbolo appartenente all'alfabeto della macchina, che è composto da 0 e 1.

Una testina magnetica in grado di leggere i simboli scritti in una cella, di scrivervi un nuovo simbolo, di muoversi in entrambi i versi lungo il nastro.

Ogni macchina di Turing è progettata per svolgere una determinata operazione: partendo da una configurazione iniziale, nella quale sul nastro sono scritti i valori su cui effettuare l'operazione, cioè l'input, arriva ad una configurazione finale in cui sul nastro è scritto il risultato, l'output.

La scrittura dei numeri è molto semplice, lo zero è rappresentato da 1, il numero uno da 11, il due da 111, il tre da 1111, e così via; il simbolo 0 è utilizzato per separare un numero dal successivo.

La macchina può trovarsi in un numero finito di stati e può compiere cinque diverse azioni:

0) scrivere 0 sulla cella in corrispondenza della quale si trova la testina;
1) scrivere 1 sulla cella in corrispondenza della quale si trova la testina;
2) spostare il nastro di una cella verso sinistra;
3) spostare il nastro di una cella verso destra;
4) arresto del sistema ed emissione del segnale di fine.

In maniera rigorosa, una macchina di Turing è definita come una tabella di quaterne del tipo (α, S, A, β) dove S è un simbolo dell'alfabeto, quindi 0 o 1, A è un'azione, e può pertanto assumere i valori 0, 1, 2, 3 o 4, e α e β sono due dei possibili stati in cui la macchina può trovarsi.

Una generica riga va letta nel seguente modo: â€œquando la macchina si trova nello stato α e legge il simbolo S, allora compie l'azione A e passa nello stato β.

La tabella rappresenta quindi le istruzioni che la macchina deve seguire.

Ogni macchina di Turing risolve un determinato problema che può anche non essere di tipo numerico (basta infatti associare ad i simboli un significato alfabetico o alfanumerico).

Turing, però, studiò anche la cosiddetta macchina universale, in grado di imitare una qualsiasi particolare macchina di Turing.

Questa macchina, per quanto possa sembrare strano, riassume la struttura funzionale di un computer.

Ma quanto è vasta la classe dei problemi risolubili da una macchina di Turing, quindi da una macchina universale, e quindi da un computer?

Una funzione si dice calcolabile se esiste una macchina di Turing che la calcola.

Secondo una celebre congettura, la tesi di Turing-Church, la classe delle funzioni calcolabili coincide con una classe di funzioni definite matematicamente, le funzioni ricorsive.

Proprio perché il concetto di "funzione calcolabile" è un concetto intuitivo, mentre quello di "funzione ricorsiva" è rigorosamente definito, non è possibile dare una dimostrazione formale della tesi di Turing-Church; pertanto si parla di 'tesi' e non di 'teorema'.

Anche se alcuni logici hanno messo in dubbio la sua validità , per il momento non è stato ancora trovato nessun controesempio alla tesi di Turing-Church ed è opinione diffusa che ci siano buone probabilità che ciò non possa avvenire.

In ogni caso, si tratta sicuramente di una classe non banale, nel senso che esistono problemi che non sono risolubili con una macchina di Turing; lo stesso Turing dimostrò che non è risolubile il problema dell'arresto:

non è possibile una macchina di Turing in grado di decidere se un'altra macchina di Turing si arresterà o no, dati uno stato e una configurazione del nastro iniziali.

I contributi del matematico inglese alla nascita e allo sviluppo dell'informatica moderna sono quindi fondamentali sotto due punti di vista: se da un lato egli scoprì una macchina in grado di svolgere i compiti di qualunque calcolatore presente o futuro (simulandone un programma), dall'altro ne mostrò anche i limiti teorici della potenza di calcolo.