Che cos’è la macchina di Turing?

Nel 1900, nell’era dell’innocenza che precede la rivoluzione introdotta nella matematica e nella logica da Kurt Gödel, David Hilbert tenne un famoso discorso al Congresso internazionale dei matematici che si svolgeva a Parigi, nel quale elencò quelli che secondo lui erano i ventitré problemi aperti più interessanti della matematica. Parecchi degli enigmi da lui proposti in quell’occasione hanno influenzato lo sviluppo di intere branche della matematica. Molti dei problemi di Hilbert rimangono ancora aperti. L’ultimo problema di Hilbert fu considerato come un passo verso il completamento del programma formalista in matematica. Esso sfidava i matematici a trovare un metodo sistematico per determinare se un enunciato matematico fosse vero o falso. Allora Hilbert credeva che questo procedimento dovesse esistere: si trattava solo di trovarlo. È evidente che, se lo si fosse trovato, esso sarebbe servito ai costruttivisti per definire l’estensione e il contenuto della matematica. Non tutti però condividevano l’opinione di Hilbert che questo metodo automatico di decisione dovesse esserci. Alcuni anni dopo, G.H. Hardy espose il seguente punto di vista:

«Questo teorema ovviamente non esiste, e questa è una fortuna, perché se esistesse possederemmo un insieme di regole meccaniche per la soluzione di tutti i problemi matematici e la nostra attività di matematici terminerebbe».

Sembra però che lo scetticismo di Hardy si basasse non sulla convinzione che questo teorema onnidecisionale fosse irraggiungibile in linea di principio, quanto piuttosto sull’opinione che l’ingegno umano non sarebbe riuscito a trovarlo e ad usarlo. Di conseguenza, la scoperta di Gödel che non esisteva alcun metodo per decidere la verità di tutti gli enunciati fu un duro colpo per i matematici. Tuttavia, nonostante vi fosse nel cuore della matematica questa indecidibilità irriducibile, restava una parte del sogno originale di Hilbert che poteva essere salvata. Anche se alcuni enunciati espressi nel linguaggio di un sistema assiomatico erano indecidibili, poteva ancora esistere un metodo sistematico per trovare tutti gli enunciati decidibili e distinguere i veri dai falsi. In tal caso, si sarebbe potuto determinare il grado relativo di incompletezza di differenti insiemi di assiomi.

Fu presto dimostrato da Alonzo Church ed Emil Post a Princeton, e da Alan Turing a Cambridge, che anche questi obiettivi più modesti erano in linea di principio irrealizzabili. Church riuscì a dimostrare che è possibile costruire formule matematiche che non possono essere valutate o di cui non si può mostrare la verità o falsità in un numero finito di passi. Qualunque calcolatore continuerebbe a funzionare all’infinito nel vano tentativo di portare a termine i calcoli. Per esempi come questi, non esiste alcun metodo che consenta di determinare se essi possono essere dimostrati oppure no. Esistono problemi insolubili.

A Cambridge, Alan Turing arrivò da solo alla stessa conclusione di Church, ma con un metodo che si sarebbe rivelato fonte di più ampie implicazioni per l’invenzione e il futuro sviluppo dei calcolatori. A differenza di Church, Turing sviluppo la sua confutazione alla congettura di Hilbert concependo un’ipotetica macchina che avrebbe dovuto decidere la verità delle proposizioni mediante una successione di operazioni ben definite. Più tardi, questi paradigmi sono diventati noti come macchine di Turing. Durante la Seconda guerra mondiale, Turing diede un importante contributo allo sviluppo della crittografia degli alleati, costruendo prototipi di dispositivi meccanici capaci di saggiare un grande numero di alternative combinatoriali, per decodificare correttamente le comunicazioni tedesche intercettate.

Una macchina di Turing è l’essenza di ogni calcolatore. Essa consiste di un nastro di memoria di lunghezza illimitata e di una unità di elaborazione dove si esplicita lo stato nel quale si trova la macchina. Lo stato presente è determinato dallo stato precedente secondo l’ultima istruzione che prescriveva come esso dovesse cambiare. Un elaboratore reale possiede svariati e curiosi accessori (schermi, capacita grafiche, software, tastiere e cosi via), che però non hanno alcun ruolo per quanto concerne la capacità logica della macchina. Sono utili strumenti che ne facilitano l’uso. Nessun calcolatore reale possiede una capacità di risoluzione dei problemi maggiore di quella della macchina idealizzata di Turing.

Tutto quello che può fare una macchina di Turing è prendere una lista di numeri naturali e trasformarla in un’altra lista di numeri naturali. Le operazioni compiute dalla macchina consistono proprio nel far corrispondere, a ciascun numero della prima lista, un numero della seconda lista. Se l’operazione che interessa è la moltiplicazione per due, allora i numeri della seconda lista saranno il doppio di quelli della prima. Vi sono, però, operazioni infinitamente più complicate, perché esistono infiniti insiemi che sono infinitamente più grandi dell’insieme infinito dei numeri naturali (per esempio tutti quei numeri, chiamati numeri irrazionali, come pi greco o la radice quadrata di due, che non si possono esprimere come frazioni ordinarie, cioè mediante il rapporto tra due numeri naturali). Essi non possono essere messi in corrispondenza con i numeri naturali. Questi insiemi infiniti vengono chiamati insiemi non numerabili.

Turing, contemporaneamente a Church, dimostrò l’esistenza di problemi matematici che non si possono decidere mediante un numero finito di calcoli logici eseguiti da una delle sue macchine ideali. Queste operazioni ineseguibili sono chiamate funzioni non calcolabili. Ad esempio, supponiamo di applicare la funzione G(N) ai numeri naturali N = 1, 2, 3, ... e definiamo che il suo valore sia eguale al valore della N-sima funzione calcolabile aumentato dell’unità, oppure sia zero, se 1’N-simo programma di calcolo non riesce a trovare una risposta in un numero finito di passi dopo che N è stato fornito come ingresso. Si vede che G non può essa stessa essere una funzione calcolabile, perché se l’N-simo programma con N come dato di ingresso venisse elaborato con successo, otterremmo il risultato impossibile che

G(N)= G(N) + 1.

Un altro insieme di esempi di funzioni non calcolabili riguarda le funzioni B(N) (dette del «castoro laborioso»), il cui valore è dato dal numero più grande che si può avere in uscita da un programma di lunghezza inferiore a N bit. Le funzioni del castoro laborioso crescono in taglia con molta maggiore rapidità di ogni funzione che si possa concepire di calcolare. Quindi, non sono calcolabili.

Molti informatici credono che una macchina di Turing sia capace di elaborare tutto ciò che può essere risolto in un tempo finito tramite una successione di operazioni fisicamente possibili: detto in altre parole, un problema è risolubile se è risolubile da una macchina di Turing. Questa è la cosiddetta «ipotesi di Church-Turing». Fino a tempi recenti si è pensato che quest’ipotesi affermasse qualcosa sulla matematica, qualcosa come: tutti i possibili modi di calcolare che si possano immaginare sono in fondo equivalenti, perché tutti possono essere ricondotti alla capacità di una macchina di Turing. Ma è chiaro che essa ci suggerisce qualcosa di più profondo sulla struttura del mondo fisico e sul fatto che noi troviamo la matematica così meravigliosamente confacente a descriverne il funzionamento.

Il fisico David Deutsch, di Oxford, ha argomentato di recente che la caratteristica che definisce le funzioni calcolabili, che per l’ipotesi di Church-Turing possono essere calcolate da una macchina di Turing, è che esse possono essere realizzate in natura. Se abbiamo due «scatole nere» una contenente un qualche processo fisico reale e l’altra una macchina di Turing ideale, per uguali dati di ingresso sarebbero possibili uscite identiche dalle due scatole. Guardando il solo risultato, non potremmo in nessun modo decidere in quale scatola esso sia stato elaborato. Quest’idea rende più serrato il legame che esiste tra matematica e leggi di natura. Accade che le leggi di natura ci permettono di costruire modelli fisici esatti che eseguono le operazioni di addizione, sottrazione, moltiplicazione e divisione. Se così non fosse, nessun dispositivo elettronico fisicamente realizzabile con silicio e metallo potrebbe calcolare le operazioni di addizione, sottrazione, moltiplicazione e divisione. Queste semplici operazioni aritmetiche sarebbero funzioni non calcolabili che noi non saremmo in grado di svolgere e di usare in dimostrazioni costruttive. Per esempio, se il nostro calcolatore non potesse fare altro che eseguire costruzioni geometriche che anche noi possiamo fare sulla carta con riga e compasso (cioè, disegnando segmenti di rette e archi di circonferenza), ne segue che non saremmo capaci di dividere in tre parti uguali un angolo per mezzo del calcolo, anche se il concetto di angolo diviso in tre parti uguali ci fosse familiare e l’esistenza di qualche linea che triseca l’angolo potesse essere dimostrata in maniera non costruttiva. L’altra faccia di questo apparente incontro tra natura e calcolo aritmetico è che esso e inaspettato e non dimostrato, se non tramite l’esperienza, e quindi non dovremmo essere sorpresi (anche se certamente lo saremmo) se si scoprisse un qualche processo fisico in natura che simula il calcolo di una funzione che non può essere calcolata da una macchina di Turing.

La corrispondenza tra realizzabilità fisica e calcolabilità sembra implicare un qualcosa che assomiglia alla verità della visione quantistica della realtà. Di certo il modo classico della fisica di Newton non possiede la proprietà di Church-Turing. Nella visione non quantistica del mondo, l’energia non si presenta in quanti discreti e numerabili. Il continuum di stati che si dà per ogni sistema fisico classico impedisce l’esistenza di una corrispondenza biunivoca tra la calcolabilità per mezzo di una successione infinita numerabile di operazioni e le leggi di natura. Deutsch, però, ha argomentato che potrebbe darsi che tutti i sistemi finiti in natura possano essere simulati per mezzo di un «calcolatore quantistico»: l’insieme di regole per questo dispositivo ipotetico può essere dedotto in termini molto generali e pare che esso abbia la capacità di eseguire calcoli molto più velocemente di qualsiasi macchina di Turing, anche se non può calcolare le funzioni che non sono calcolabili con una macchina di Turing. Ma ciò che più sorprende è il fatto che il calcolo quantistico sembra richiedere l’esistenza oggettiva della realtà quantistica. Ciò è possibile solamente nell’interpretazione della teoria quantistica detta dei «molti mondi», e fa sperare che un giorno esisterà una soluzione sperimentale del problema dell’ontologia quantistica.