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 1936. Il Teorema di Turing è in un certo senso la "versione informatica" del teorema di indecidibilità 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 N0. Ora modifichiamo leggermente il programma N0 creando un nuovo programma N1 che prende in input il codice di un programma P e quindi calcola N0(P,P); questo nuovo programma stabilisce cosa stampa P quando riceve come input il codice di se stesso. A questo punto modifichiamo ancora leggermente N1 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 in input a N, chiedendogli di dirci cosa farebbe se stesso ricevendo in input se stesso. 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 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.