Questo teorema, spiegatoci nelle prime lezioni del corso di “Linguaggi di Programmazione” (3° anno LT in Informatica), mi ha fin da subito affascinato… e mò ve lo ri-scrivo in inglese.
Si tratta del problema della decidibilità o indecidibilità della terminazione dei programmi.
P = turing machine
x = string
by hypothesis
we suppose that it’s possible to build a program Q that
Q(P,x) = halts
if and only if P(x) halts
Q(P,x) = does not halt
if and only if P(x) does not
notice that Q always halts for every P and x.
it must be verified that Q can exist.
a simple step forward…
Q(P,P) = halts
if and only if P(P) halts
Q(P,P) = does not halt
if and only if P(P) does not
P is itself a string! nothing esoteric…
so, we can also build a program D that uses Q in this way…
D(P) = halt
if and only if P(P) runs forever
that is Q(P,P) = does not halt
D(P) = run forever
if and only if P(P) halts
that is Q(P,P) = halts
using the hypothesis that the program Q (that says the termination of a program can be decided)
another simple step forward…
replace P with D… it’s a string itself and it’s also a Turing Machine… isn’t it?
D(D) = halts
if and only if Q(D,D) runs forever
D(D) = runs forever
if and only if Q(D,D) halts
in this way… D(D) executes Q(D,D)… but…what?
D(D) says “yes” if Q(D,D) says “no”?
that is
D(D) halts if D(D) runs forever
D(D) runs forever if D(D) halts
it doesn’t make any sense… it’s a contradiction!!!
well the hypothesis is wrong… the halting problem is undecidable.
Q.E.D
-A
tratto da “Concepts in Programming Languages” John C. Mitchell
