Peatumisprobleem: määratlus ja Turingi tõestus
Peatumisprobleem ja Turingi tõestus selgitatud lihtsalt: miks universaalset peatuse-otsustajat ei eksisteeri, mõttekäik, koodinäited ja lahendamatuse tõestus.
Peatumisprobleem (inglise keeles halting problem) on arvutiteaduse klassikaline otsustamise probleem. Küsimus on lihtne: kas eksisteerib algoritm, mis suudab võtta mistahes programmi F ja sisendi I ning otsustada täpselt, kas F(I) peatub (st lõpetab töö) või jookseb lõpmatusse tsüklisse? Kui sellist algoritmi oleks, siis ütleksime, et peatumisprobleem on otsustatav (decidable).
Näited lihtsatest programmidest (pseudokood):
while True: continue; # jookseb igavesti
while False: continue; # peatub kohe (ei sisene tsüklisse)
Tõestuse idee (Turingi enda argument)
Oletame vastupidist: et olemas on programm H, mis otsustab peatumisprobleemi. Me võtame tavapärase jaotuse: H(F, I) tagastab true, kui programm F koos sisendiga I peatub, ja false, kui F(I) ei peatu (st jookseb igavesti). See on otsustaja, mis ütleb täpselt, kas antud programm peatub.
Kui meil on selline H, saame ehitada uue programmi R, mis kasutab H-d enda sisendina antud programmi kohta otsustamiseks ja käitub seejärel vastupidiselt H-i ennustusele. Pseudokoodina võime defineerida:
def R(F):
if H(F, F):
while True: continue # kui H ütleb, et F(F) peatub, siis R läheb lõpmatusse tsüklisse
else:
return # kui H ütleb, et F(F) ei peatu, siis R peatub
Nüüd vaatame, mis juhtub, kui anname R iseendale sisendiks, st vaatleme R(R). On kaks võimalust:
Kokkuvõttes põhjustab eeldus, et H eksisteerib, loogilise vastuolu: H peab nii ennustama, et R(R) peatub kui ka mitte-peatub samaaegselt. See näitab, et sellist üldist otsustajat H ei saa olemas olla. Seega peatumisprobleem on otsustamatu (undecidable).
Mõningad täpsustused ja tagajärjed
- Tõestusmeetod: tegemist on vastuväite (contradiction) ja diagonaaltehnika kombinatsiooniga: ehitatakse programm, mis käitub vastupidiselt oletatavale otsustajale, kasutades programmi enda koodi kui sisendit (eneseviide).
- Formaalselt: ei eksisteeri üldist algoritmi H(P, I), mis alati lõpeks ja annaks õige vastuse "jah" täpselt siis, kui programm P sisendil I peatub.
- Poolotsustatavus (semi-decidability): kuigi peatumisprobleem on otsustamatu, on see poolotsustatav (recursively enumerable): kui programm P(I) tõepoolest peatub, saab seda näidata, käivitades P(I) ja ootades, kuni see peatub. Kuid kui P(I) ei peatu, siis otsa ei näe ja ei saa kindlalt väita, et see ei peatu — pole üldist lõpetavat testi mitte-peatumise tõestamiseks.
- Mõju: peatumisprobleemi mittevastuvõtmine näitab fundamentaalseid piire, mida arvutid ja algoritmid ei saa ületada. Selle tulemusel tekivad mitu teist mittetõestatavat/otsustamatut probleemi (näiteks paljud programmeerimiskeelte omadusi käsitlevad küsimused), ning on loodud mitmeid teoreetilisi tööriistu (nt Rice'i teoreem), mis võimaldavad näidata teiste probleemide otsustamatust.
See fundamentaalne tulemus avastati ja vormistati Alan Turingi poolt 1936. aastal, mille järel halting-probleemist on saanud üks arvutiteooria keskseid näiteid piiridest, mida arvutus suuteline on lahendada.
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.
Otsige