THE HALTING PROBLEM

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

conceptsprogramming.jpg

Lascia un commento

Effettua il login con uno di questi metodi per inviare il tuo commento:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger cliccano Mi Piace per questo: