Teorema di Turing

Il teorema di Turing asserisce l'esistenza di problemi non decidibili, per i quali cioè non esiste alcun algoritmo in grado di dare una risposta in tempo finito su tutte le istanze del problema. La dimostrazione di questo risultato si deve ad Alan Turing, che lo provò in un articolo del 1937. Il Teorema di Turing è in un certo senso la "versione informatica" del teorema di incompletezza di Gödel.

Dimostrazione

Un accenno di dimostrazione viene dato di seguito.
Supponiamo di avere alcuni programmi che stampano sempre o "si" o "no" in output, qualsiasi sia il loro input. Il nostro problema sarà definito come segue:

Dato sotto forma di codice un programma P che stampa sempre "si" oppure "no" ed un input I, stabilire l'output P(I).

Mostreremo per assurdo che non esiste alcun algoritmo in grado di dare una risposta per tutte le possibili coppie (P,I) di programmi ed input. Supponiamo quindi per assurdo l'esistenza di un programma che, preso il codice di un altro programma P, ci dica se esso stampa "si" oppure "no" quando esso riceve un certo input I; l'input del nostro ipotetico programma è quindi una coppia (P,I), mentre l'output è P(I). Chiamiamo questo programma $N_{0}$. Ora modifichiamo leggermente il programma $N_{0}$ creando un nuovo programma $N_{1}$ che prende in input il codice di un programma P e quindi calcola $N_{0}(P,P)$; questo nuovo programma stabilisce cosa stampa P quando riceve come input il codice di sé stesso. A questo punto modifichiamo ancora leggermente $N_{1}$ in modo che esso stampi "no" quando il programma analizzato stampa "si" e viceversa; chiamiamo tale programma N (non esistente); notiamo che questo è appunto un programma che stampa sempre o "si" o "no". A questo punto chiediamoci lecitamente:

Cosa stampa N quando riceve in input N?

In pratica stiamo dando N come input a sé stesso, chiedendogli dunque di dirci cosa farebbe sé stesso ricevendo sé stesso come input. Ora, se la copia di N che viene analizzata stampasse "si" quando riceve N in input, allora il programma N analizzatore, che ha ricevuto proprio N in input, stamperebbe "no"; ma questo è assurdo. Viceversa, se l'N analizzato stampasse "no", allora N stamperebbe "si"; ma anche questo è assurdo. Pertanto tale programma non può esistere.

La versione originale della dimostrazione di Turing è in realtà basata sul problema della fermata, detto anche problema dell'arresto; si dimostra cioè che non può esistere un programma che possa decidere se un qualsiasi programma si arresti o continui a procedere all'infinito.

Una dimostrazione più formale richiede alcune nozioni di informatica teorica, come la conoscenza dei linguaggi formali e delle Macchine di Turing.