Marco Mattiucci

INFORMATICA - SISTEMI DI ELABORAZIONE
"The Halting Problem"

Supponiamo che esista un programma H per computer che, prendendo come input un qualsiasi altro programma x (una sequenza di bit), ne possa stabilire, dietro elaborazione su una UTM (Universal Turing Machine - per essere sufficientemente generali), se l'esecuzione di x terminerà o meno in un tempo finito (halting problem) dando questa indicazione come output. Quindi, ad esempio, se UTM(H,x) produce 1 il programma valutato x termina la sua esecuzione in un tempo finito, al contrario se UTM(H,x) produce 0 il programma x continua la sua esecuzione all'infinito.

Basta ora costruire un programma L, sulla stessa UTM, del tipo UTM(L,x) = se UTM(H,x) è 1 entra in loop (non terminare mai), altrimenti stop. Cosa accade se proviamo a dare come input L ad L? Ossia cosa significa UTM(L,L) e cosa produce?

UTM(L,L) ferma la sua esecuzione se (come da definizione di L, sostituendo) UTM(H,L) è diverso da 1 ossia se (come da definizione di H, sostituendo) L non termina mai. Questa è una contraddizione! Ne consegue falsa l'ipotesi iniziale che possa esistere H.

Questa dimostrazione, fatta da Turing, evidenzia un problema che non è affrontabile dalla macchina di Turing stessa e quindi dalla computazione automatica (dai computer) in generale. Essa ha molto a che vedere con il Teorema di Godel sull'incompletezza dei sistemi formali (che potete trovare brevemente nella sezione di matematica di questo sito).

marcomattiucci.it

• Home

Informatica:

• Home(Informatica)

Sistemi complessi:

• Home(Complessità)
• K-Complessità
• K-Casualità
• K-Compressione
• K-Probabilità
• Micro e Macro Stato
• Emersione
• "The halting problem"
• Irriducibilità
• Il Determinismo