Quando si dice che un problema «non è risolvibile da alcun algoritmo», si fa un'affermazione molto forte. Per renderla precisa serve una definizione matematica di algoritmo. La tesi di Church-Turing afferma che le funzioni calcolabili da un procedimento meccanico effettivo sono esattamente quelle calcolabili da una macchina di Turing. È il ponte fra un'idea intuitiva, «procedura eseguibile passo passo», e un oggetto formale. Qui la esamino come concetto, insieme ai modelli alternativi che la sostengono.
Perché è una tesi e non un teorema
Un teorema collega due oggetti matematici. La tesi di Church-Turing collega un oggetto matematico, la macchina di Turing, a una nozione informale, quella di procedimento effettivo. Non si può dimostrare nel senso stretto, perché uno dei due termini non ha una definizione rigorosa. Si può solo raccogliere evidenza a favore.
L'evidenza principale è sorprendente: modelli di calcolo nati in modo indipendente, con idee di partenza molto diverse, si sono rivelati tutti equivalenti alla macchina di Turing. Nessuno ha mai proposto un modello ragionevole, cioè fisicamente realizzabile con passi finiti e deterministici, che calcoli qualcosa in più.
Primo modello: il lambda calcolo
Il lambda calcolo non ha nastri né stati. Ha solo funzioni. I termini si costruiscono con tre regole:
- una variabile x è un termine;
- un'astrazione λx.M è un termine: la funzione che a x associa M;
- un'applicazione (M N) è un termine: la funzione M applicata all'argomento N.
Il calcolo procede con una sola regola, la β-riduzione: (λx.M) N si riscrive come M con N al posto di x. Per esempio (λx.x x) y si riduce a y y.
Non ci sono numeri, ma si possono codificare. Nella codifica di Church il numero n è la funzione che applica n volte il primo argomento al secondo:
0 = λf.λx. x
1 = λf.λx. f x
2 = λf.λx. f (f x)
successore = λn.λf.λx. f (n f x)
Con codifiche simili si rappresentano booleani, coppie, liste e ricorsione (tramite combinatori di punto fisso). Il risultato è che le funzioni sui naturali definibili nel lambda calcolo sono esattamente quelle calcolabili da una macchina di Turing.
Secondo modello: le funzioni ricorsive
Questo approccio parte da funzioni di base sui numeri naturali e chiude l'insieme rispetto ad alcune operazioni.
Funzioni di base: la costante zero, il successore n ↦ n + 1, le proiezioni che restituiscono uno degli argomenti.
Operazioni:
- composizione: da f e g si ottiene f(g(x));
- ricorsione primitiva: si definisce h(x, 0) e h(x, n + 1) in funzione di h(x, n), come in un ciclo for con numero di iterazioni noto;
- minimizzazione (operatore μ): μy[f(x, y) = 0] è il più piccolo y per cui f vale zero, cercato provando y = 0, 1, 2, …
Senza la minimizzazione si ottengono le funzioni ricorsive primitive, che terminano sempre: somma, prodotto, potenza, fattoriale e quasi tutto ciò che si usa in pratica. Ma non tutte le funzioni calcolabili e totali sono ricorsive primitive: la funzione di Ackermann cresce troppo in fretta per esserlo.
Con la minimizzazione, che corrisponde a un ciclo while senza limite noto, si ottengono le funzioni μ-ricorsive, che possono non terminare. Esse coincidono con le funzioni Turing-calcolabili. La differenza fra ciclo for e ciclo while è, in questo senso, la differenza fra garanzia di terminazione e piena potenza di calcolo.
Terzo modello: le macchine a registri
Una macchina a registri ha un numero finito di registri, ciascuno contenente un numero naturale arbitrario, e un programma con istruzioni numerate:
- INC r: incrementa il registro r;
- DEC r, k: se r è positivo lo decrementa, altrimenti salta all'istruzione k;
- HALT.
Bastano queste tre istruzioni per calcolare tutto ciò che calcola una macchina di Turing. Anzi, bastano due registri con un'opportuna codifica dei dati. Il modello è vicino all'architettura dei processori reali.
Turing-completezza
Un sistema si dice Turing-completo se può simulare una macchina di Turing qualsiasi, a patto di avere memoria sufficiente. Sono Turing-completi tutti i linguaggi di programmazione generali, ma anche sistemi inattesi: alcuni automi cellulari, come il Gioco della vita di Conway, e diversi meccanismi nati per altri scopi, come certi sistemi di macro e di template.
La conseguenza pratica è doppia:
- un sistema Turing-completo può esprimere qualunque calcolo;
- un sistema Turing-completo eredita tutte le indecidibilità: per i suoi programmi non si può decidere in generale la terminazione né, per il teorema di Rice, alcuna proprietà semantica non banale.
Per questo chi progetta formati di configurazione, linguaggi di query o regole di filtro a volte sceglie deliberatamente un linguaggio non Turing-completo: rinuncia a un po' di espressività per ottenere garanzie, come la terminazione di ogni valutazione.
Che cosa la tesi non dice
La tesi riguarda che cosa si può calcolare, non quanto costa. Modelli equivalenti per calcolabilità possono differire molto in efficienza. Esiste una versione «estesa» della tesi, secondo cui ogni modello ragionevole si simula con una macchina di Turing con un rallentamento al più polinomiale; questa versione è molto più discussa, e il calcolo quantistico è il principale motivo di dubbio.
In sintesi
- La tesi di Church-Turing identifica il calcolo effettivo con quello delle macchine di Turing.
- Non si dimostra, perché collega una nozione intuitiva a una formale, ma è sostenuta dall'equivalenza di molti modelli.
- Lambda calcolo, funzioni μ-ricorsive e macchine a registri calcolano esattamente le stesse funzioni.
- Le funzioni ricorsive primitive terminano sempre ma non coprono tutto: Ackermann ne è fuori.
- Un sistema Turing-completo ottiene piena espressività al prezzo di tutte le indecidibilità.
