La macchina più importante mai costruita

Il calcolo è un concetto familiare che la maggior parte di noi capisce intuitivamente. Prendi la funzione f(x) = x + 3. Quando x è tre, f(3) = 3 + 3. Sei. Facile. Sembra ovvio che questa funzione sia calcolabile. Ma alcune funzioni non sono così semplici e non è così facile determinare se possono essere calcolate, il che significa che potrebbero non darci mai una risposta definitiva.

Nel 1928, i matematici tedeschi David Hilbert e Wilhelm Ackermann proposero una domanda chiamata Problema di Entscheidung (“problema decisionale”). Col tempo, la loro domanda avrebbe portato a una definizione formale di computabilità, che avrebbe permesso ai matematici di rispondere a una serie di nuovi problemi e gettato le basi per l'informatica teorica.

La definizione venne da uno studente laureato di 23 anni di nome Alan Turing, che nel 1936 scrisse un documento seminale che non solo formalizzò il concetto di computazione, ma si dimostrò anche una questione fondamentale della matematica e creò le basi intellettuali per l'invenzione del calcolatore elettronico. La grande intuizione di Turing è stata quella di fornire una risposta concreta alla domanda di calcolo sotto forma di una macchina astratta, in seguito chiamata la macchina di Turing dal suo consulente di dottorato, Alonzo Church. È astratto perché non esiste (e non può) esistere fisicamente come dispositivo tangibile. Invece, è un modello concettuale di calcolo: se la macchina può calcolare una funzione, allora la funzione è calcolabile.

Ecco come funziona. Una macchina di Turing può leggere e alterare i simboli su un nastro infinitamente lungo, come dettato da una tabella di regole. Il nastro è composto da "celle", ognuna delle quali può memorizzare esattamente un simbolo, e la macchina legge e riscrive il contenuto delle celle con una testina del nastro. Ogni regola nella tabella determina cosa dovrebbe fare la macchina in base sia al suo stato attuale che al simbolo che sta leggendo. La macchina può entrare in uno stato finale ("stato di accettazione" o "stato di rifiuto") in cui si ferma, accettando o rifiutando l'input. Oppure cade in un ciclo infinito e continua a leggere il nastro per sempre.

Il modo migliore per comprendere una macchina di Turing è considerare un semplice esempio. Immaginiamone uno progettato per dirci se un dato input è il numero zero. Useremo il numero di input 0001 accompagnato da simboli vuoti (#), quindi "#0001#" è la parte rilevante del nostro nastro.

La macchina si avvia nello stato iniziale, che chiameremo q0. Legge la cella più a sinistra del nostro nastro e trova uno spazio vuoto. Le regole dicono: "Quando sei nello stato q0, se il simbolo è #, lascialo com'è senza modifiche, sposta una cella a destra e cambia lo stato della macchina in q1". Dopo questo passaggio, la macchina è nello stato q1 e la sua testa sta leggendo il secondo simbolo, 0.

Ora cerchiamo una regola che si applichi a queste condizioni. Ne troviamo uno che dice: "Rimani nello stato q1 e sposta la testa di una cella a destra". Questo ci lascia nella stessa posizione (nello stato q1, leggendo "0"), quindi continuiamo a spostarci verso destra finché la testa finalmente legge un numero diverso, l'1.

Quando consultiamo nuovamente la tabella, troviamo una nuova regola: "Se incontriamo un 1, transizione a q2, che è uno stato di 'rifiuto'". La macchina si ferma, rispondendo "No" alla domanda originale, "'0001' è zero?"

Se invece l'input è "#0000#", la macchina incontrerà un # dopo tutti quegli zeri. Quando consultiamo la tabella, troviamo una regola che dice che questo significa che la macchina entra nello stato q3, uno stato di “accettazione”. Ora la macchina risponde "Sì" alla domanda "'0000' è zero?"

Con la sua macchina astratta, Turing ha stabilito un modello di calcolo per rispondere all'Entscheidungsproblem, che chiede formalmente: Dato un insieme di assiomi matematici, esiste un processo meccanico - un insieme di istruzioni, che oggi chiameremmo un algoritmo - che può sempre determinare se una data affermazione è vera?

Diciamo che vogliamo trovare un algoritmo che possa dirci se una certa posizione degli scacchi è possibile. Qui, gli assiomi sono le regole degli scacchi che governano le mosse legali. Possiamo seguire una sequenza finita di procedure passo dopo passo per arrivare a quella posizione? Sebbene alcune posizioni possano richiedere più tempo della nostra vita per essere analizzate - un algoritmo può generare tutte le posizioni possibili e confrontare ciascuna di esse con l'input - tali algoritmi esistono nel gioco degli scacchi. Di conseguenza, diciamo che gli scacchi sono "decidibili".

Tuttavia, nel 1936, Church e Turing, utilizzando metodi diversi, dimostrarono in modo indipendente che non esiste un modo generale per risolvere ogni istanza dell'Entscheidungsproblem. Ad esempio, alcuni giochi, come Game of Life di John Conway, sono indecidibili: nessun algoritmo può determinare se un determinato schema apparirà da uno schema iniziale.

Turing ha dimostrato che una funzione è calcolabile se esiste un algoritmo in grado di eseguire il compito desiderato. Allo stesso tempo, ha dimostrato che un algoritmo è un processo che può essere definito da una macchina di Turing. Quindi, una funzione calcolabile è una funzione che ha una macchina di Turing per calcolarla. Questo può sembrare un modo tortuoso per definire la computabilità, ma è il meglio che abbiamo. "Non è che tu abbia la possibilità di definirlo in qualche altro modo", ha detto Michael Sipser, scienziato informatico teorico presso il Massachusetts Institute of Technology. "Penso che sia comunemente accettato che la tesi di Church-Turing affermi che la nozione informale di algoritmo corrisponde a ciò che qualsiasi modello computazionale 'ragionevole' può fare." Altri matematici hanno escogitato diversi modelli di calcolo che sembrano piuttosto diversi in superficie ma in realtà sono equivalenti: possono eseguire qualsiasi calcolo che le macchine di Turing possono fare e viceversa.

Solo pochi anni dopo Kurt Gödel aveva dimostrato che la matematica era incompleto, Church e Turing hanno mostrato con questo lavoro che alcuni problemi in matematica sono indecidibili: nessun algoritmo, per quanto sofisticato, può dirci se la risposta è sì o no. Entrambi furono colpi devastanti per Hilbert, che aveva sperato che la matematica avrebbe avuto risposte ordinate e idealizzate. Ma forse è meglio così: se esistesse una soluzione generale all'Entscheidungsproblem, significherebbe che tutti i problemi matematici potrebbero essere ridotti a semplici calcoli meccanici.

Oltre a rispondere a queste domande fondamentali, la macchina di Turing ha anche portato direttamente allo sviluppo dei computer moderni, attraverso una variante nota come macchina universale di Turing. Questo è un tipo speciale di macchina di Turing in grado di simulare qualsiasi altra macchina di Turing su qualsiasi input. Può leggere una descrizione di altre macchine di Turing (le loro regole e nastri di input) e simulare i loro comportamenti sul proprio nastro di input, producendo lo stesso output che produrrebbe la macchina simulata, proprio come i computer di oggi possono leggere qualsiasi programma ed eseguirlo. Nel 1945, John von Neumann propose un'architettura di computer, chiamata architettura di von Neumann, che rendeva possibile il concetto universale di macchina di Turing in una macchina reale.

Quando Sanjeev Arora, un informatico teorico alla Princeton University, insegna questo concetto, sottolinea un quadro filosofico più ampio. "Ci sono due nozioni di 'universale'", ha detto. “Una nozione dell'universale è che può far funzionare qualsiasi altra macchina di Turing. Ma l'altra nozione più ampia di "universale" è che può eseguire qualsiasi calcolo che ti viene in mente nell'universo. Nel mondo della fisica classica, qualsiasi processo fisico può essere modellato o simulato utilizzando algoritmi che, a loro volta, possono essere simulati da una macchina di Turing.

Un'altra variante notevole e sempre più utile è la macchina probabilistica di Turing. A differenza di una normale macchina di Turing, che ha una reazione ben definita a ogni input, una macchina di Turing probabilistica può avere più reazioni basate sulle probabilità. Ciò significa che può produrre risultati diversi per lo stesso input in momenti diversi. Sorprendentemente, questo tipo di strategia probabilistica può essere più efficiente di un approccio puramente deterministico per determinati problemi. Le idee delle macchine di Turing probabilistiche si sono dimostrate praticamente utili in aree come la crittografia, l'ottimizzazione e l'apprendimento automatico.

Queste macchine astratte sono forse la migliore prova che porre domande fondamentali può essere tra le cose più utili che uno scienziato possa fare.