Problem zaustavitve
Haltingov problem je problem v računalništvu. Gre za računalniški program, pri katerem je treba ugotoviti, ali bo program tekel večno ali ne. Pravimo, da program "rešuje problem ustavljanja", če lahko pogleda katerikoli drug program in pove, ali bo ta program tekel večno ali ne.
Na primer, program, kot je ta:
while True: nadaljujte;se bo vrtela v nedogled, vendar bo program
while False: nadaljujte;se zelo hitro ustavi.
Ali obstaja program, ki rešuje problem ustavljanja? Izkazalo se je, da ni. To dejstvo dokažemo tako, da pokažemo, da če obstaja program, ki rešuje problem zaustavitve, se zgodi nekaj nemogočega. Zato se bomo za zdaj obnašali, kot da program, ki rešuje problem zaustavitve, res obstaja. Tu je P funkcija, ki bo ovrednotila funkcijo F (klicano z argumentom I) in vrnila true, če teče večno, in false v nasprotnem primeru.
def P(F, I): if F(I) teče večno: return True; else: return False;P si lahko ogledate kateri koli program in ugotovite, ali bo deloval večno ali ne. S programom P ustvarimo nov program, ki ga bomo poimenovali Q. Q si ogleda drug program in nato odgovori na naslednje vprašanje: "Če zaženemo ta program in ga prisilimo, da si ogleda kopijo samega sebe, ali bo deloval večno?". Q lahko naredimo, ker imamo P. Vse, kar moramo storiti, je, da Q povemo, naj ustvari nov program, ki je stari program, ki gleda samega sebe, nato pa s P ugotovimo, ali novi program teče večno ali ne.
def Q(F): vrni P(F, F);Zdaj naredimo še en program R. R pogleda drug program in vpraša Q za odgovor na ta program. Če Q odgovori: "Da, če zaženemo ta program in ga prisilimo, da pogleda kopijo samega sebe, bo deloval večno", se R ustavi. Če Q odgovori "ne, če ta program zaženemo in ga prisilimo, da si ogleda kopijo samega sebe, ne bo tekel večno", potem R vstopi v neskončno zanko in teče večno.
def R(F): if Q(F): return; //terminate else: while True: continue; //loop foreverZdaj si bomo ogledali, kaj se zgodi, če R pogledamo v kopijo samega sebe. Zgodi se lahko dvoje: ali se bo ustavil ali pa bo deloval v nedogled.
Če zagon programa R in njegov pogled na kopijo samega sebe ne traja večno, potem je Q odgovoril: "Da, če zaženemo ta program in ga prisilimo, da pogleda na kopijo samega sebe, bo trajal večno." Toda Q je to rekel, ko je gledal sam R. Torej je Q dejansko rekel: "da, če zaženemo program R in ga prisilimo, da pogleda kopijo samega sebe, bo deloval večno". Torej: Če R, ki teče na kopiji samega sebe, ne teče večno, potem teče večno. To je nemogoče.
Če program R, ki ga zaženemo in ga prisilimo, da pogleda kopijo samega sebe, deluje večno, potem je Q odgovoril: "Ne, če zaženemo ta program in ga prisilimo, da pogleda kopijo samega sebe, ne bo deloval večno." Toda Q je to rekel, ko je gledal sam R. Torej je Q dejansko rekel: "ne, če zaženemo program R in ga prisilimo, da pogleda kopijo samega sebe, ne bo deloval večno". Torej: Če R, ki teče na kopiji samega sebe, teče večno, potem ne teče večno. Tudi to je nemogoče.
Ne glede na to, kaj se zgodi, se znajdemo v nemogoči situaciji. Nekaj smo naredili narobe in ugotoviti moramo, kaj je bilo narobe. Večina stvari, ki smo jih naredili, ni bila napačna. Ne moremo reči, da je "napačno, če program pogleda kopijo samega sebe", ali da je "napačno, če pogledamo, kaj je rekel drug program, in gremo v zanko, če je rekel eno, in se ustavimo, če je rekel drugo". Ni smiselno reči, da teh stvari ne smemo početi. Edina stvar, za katero se zdi, da bi lahko bila napačna, je ta, da smo se pretvarjali, da program, kot je P, sploh obstaja. In ker je to edina stvar, ki bi lahko bila napačna, in nekaj mora biti napačno, je to to. To je dokaz, da program, kot je P, ne obstaja. Ne obstaja program, ki bi reševal problem zaustavitve.
Ta dokaz je leta 1936 našel Alan Turing.
Vprašanja in odgovori
V: Kaj je Halting problem?
O: Problem zaustavitve je problem v računalništvu, ki obravnava računalniški program in določa, ali bo program tekel večno ali ne.
V: Kako vemo, ali program rešuje problem zaustavitve?
O: Pravimo, da program "rešuje problem ustavljanja", če lahko pogleda katerikoli drug program in pove, ali bo ta program tekel večno ali ne.
V: Ali lahko dokažemo, da tak program ne obstaja?
O: Da, tako, da pokažemo, da bi se v primeru obstoja takega programa zgodilo nekaj nemogočega. Ta dokaz je leta 1936 našel Alan Turing.
V: Kaj naredi P?
O: P je funkcija, ki ovrednoti drugo funkcijo F (klicano z argumentom I) in vrne true, če teče večno, in false v nasprotnem primeru.
V: Kaj počne Q?
O: Q pogleda drug program in nato odgovori na vprašanje, ali bo izvajanje istega programa na sebi povzročilo neskončno zanko ali ne. To stori tako, da uporabi P za vrednotenje dane funkcije F.
V: Kaj naredi R?
O: R pogleda drug program in vpraša Q za odgovor na ta program. Če Q odgovori "da, če zaženemo ta program in ga prisilimo, da pogleda na kopijo samega sebe, bo tekel večno", se R ustavi; če pa Q odgovori "ne, če zaženemo ta program in ga prisilimo, da pogleda na kopijo samega sebe, ne bo tekel večno", potem R vstopi v neskončno zanko in teče večno.
V: Kaj se zgodi, če prisilimo R, da pogleda samega sebe?
O: Zgodita se lahko dve stvari - ali se R ustavi ali teče v nedogled - vendar sta oba rezultata nemogoča glede na to, kar je bilo dokazano o tem, da programi, kot je P, ne obstajajo, zato je moralo nekje na poti do tega, da je R pogledal samega sebe, iti nekaj narobe.
