Peatumisprobleem

Halting-probleem on probleem arvutiteaduses. Probleem seisneb selles, et vaadelda arvutiprogrammi ja leida, kas programm töötab igavesti või mitte. Me ütleme, et programm "lahendab haltinguprobleemi", kui ta suudab vaadata mõnda teist programmi ja öelda, kas see teine programm jookseb igavesti või mitte.

Näiteks selline programm:

while True: continue;

hakkab igavesti loopima, kuid programm

while False: continue;

peatub väga kiiresti.

Kas on olemas programm, mis lahendab peatumisprobleemi? Selgub, et ei ole. Me tõestame seda asjaolu, näidates, et kui on olemas programm, mis lahendab peatumisprobleemi, siis juhtub midagi võimatut. Seega teeme hetkel nii, nagu oleks tõesti olemas programm, mis lahendab peatumisprobleemi. Siin on P funktsioon, mis hindab funktsiooni F (kutsutakse argumendiga I) ja tagastab true, kui see jookseb igavesti, ja false, kui mitte.

def P(F, I): if F(I) jookseb igavesti: return True; else: return False;

P saab vaadata mis tahes programmi ja teada, kas see töötab igavesti või mitte. Me kasutame P, et teha uus programm, mida me nimetame Q. Mida Q teeb, on see, et ta vaatab teist programmi ja vastab seejärel järgmisele küsimusele: "Kui me käivitame selle programmi ja paneme selle vaatama enda koopiat, kas see jookseb igavesti?". Me saame teha Q, sest meil on olemas P. Meil on vaja ainult öelda Q-le, et ta looks uue programmi, mis on vana programm, mis vaatab iseennast, ja seejärel kasutada P-d, et teada saada, kas uus programm jookseb igavesti või mitte.

def Q(F): return P(F, F);

Nüüd teeme teise programmi R. R vaatab teist programmi ja küsib selle programmi kohta vastust Q. Kui Q vastab "jah, kui me käivitame selle programmi ja paneme selle vaatama enda koopiat, siis jookseb see igavesti", siis R peatub. Kui Q vastab "ei, kui me käivitame selle programmi ja paneme selle vaatama enda koopiat, siis ei jookse see igavesti", siis siseneb R lõpmatusse tsüklisse ja jookseb igavesti.

def R(F): if Q(F): return; //lõpeb muidu: while True: continue; //loop igavesti

Nüüd vaatame, mis juhtub, kui paneme R-i vaatama enda koopiat. Võib juhtuda kaks asja: see kas peatub või jookseb igavesti.

Kui R-i käivitamine ja selle enda koopia vaatamine ei jookse igavesti, siis Q vastas "jah, kui me käivitame selle programmi ja paneme selle enda koopiat vaatama, siis jookseb see igavesti". Kuid Q ütles seda, kui ta vaatab R-i ennast. Seega ütles Q tegelikult: "jah, kui me käivitame programmi R ja paneme selle vaatama enda koopiat, siis jookseb see igavesti". Niisiis: Kui R iseenda koopiat käivitades ei jookse igavesti, siis jookseb ta igavesti. See on võimatu.

Kui R-i käivitamine ja selle enda koopia vaatamiseks panemine kestab igavesti, siis Q vastas "ei, kui me käivitame selle programmi ja paneme selle enda koopiat vaatama, siis ei jookse see igavesti". Aga Q ütles seda, kui ta vaatab R-i ennast. Seega ütles Q tegelikult: "ei, kui me käivitame programmi R ja paneme selle vaatama enda koopiat, siis see ei jookse igavesti". Nii et: Kui R töötab enda koopia peal igavesti, siis ei jookse ta igavesti. Ka see on võimatu.

Ükskõik, mis ka ei juhtuks, saame võimatu olukorra. Me tegime midagi valesti ja peame välja selgitama, mis see oli. Enamik asju, mida me tegime, ei olnud valesti. Me ei saa öelda, et "programmi enda koopiat vaatama panemine on vale" või et "teise programmi vaatamine ja seejärel tsüklisse minek, kui see ütles üht asja, ja peatumine, kui see ütles midagi muud" on vale. Ei ole mõtet öelda, et me ei tohi neid asju teha. Ainus asi, mida me tegime, mis tundub olevat vale, on see, et me teesklesime, et selline programm nagu P on üldse olemas. Ja kuna see on ainus asi, mis võiks olla vale, ja midagi peab olema vale, siis see ongi see. See on tõestus, et sellist programmi nagu P ei ole olemas. Pole olemas programmi, mis lahendaks peatumisprobleemi.

Selle tõestuse leidis Alan Turing 1936. aastal.

Küsimused ja vastused

K: Mis on Haltingi probleem?

V: Halting-probleem on probleem arvutiteaduses, mis vaatleb arvutiprogrammi ja määrab, kas programm töötab igavesti või mitte.

K: Kuidas me teame, kas programm lahendab Halting-probleemi?

V: Me ütleme, et programm "lahendab Halting-probleemi", kui ta suudab vaadata mis tahes teist programmi ja öelda, kas see teine programm töötab igavesti või mitte.

K: Kas on võimalik tõestada, et sellist programmi ei ole olemas?

V: Jah, näidates, et kui selline programm oleks olemas, siis juhtuks midagi võimatut. Selle tõestuse leidis Alan Turing 1936. aastal.

K: Mida teeb P?

V: P on funktsioon, mis hindab teist funktsiooni F (mida kutsutakse argumendiga I) ja tagastab tõene, kui see töötab igavesti, ja muidu vale.

K: Mida teeb Q?

V: Q vaatleb teist programmi ja vastab seejärel küsimusele, kas sama programmi käivitamine iseendale annab tulemuseks lõpmatu tsükli või mitte. Ta teeb seda, kasutades P abil antud funktsiooni F hindamist.

K: Mida teeb R?

V: R vaatab teist programmi ja küsib Q-lt vastust selle konkreetse programmi kohta. Kui Q vastab "jah, kui me käivitame selle programmi ja paneme selle enda koopiat vaatama, siis jookseb see igavesti", siis R peatub; kui aga Q vastab "ei, kui me käivitame selle programmi ja paneme selle enda koopiat vaatama, siis ei jookse see igavesti", siis läheb R lõpmatusse tsüklisse ja jookseb igavesti.

K: Mis juhtub, kui paneme R-i ennast vaatama?

V: Võib juhtuda kaks asja - kas R peatub või jookseb igavesti - kuid mõlemad tulemused on võimatud vastavalt sellele, mida on tõestatud, et selliseid programme nagu P ei eksisteeri, seega peab midagi olema kusagil valesti läinud, mis viis selleni, et panna R ennast vaatama.