Sustabdymo problema
Haltingo problema yra informatikos problema. Ši problema - tai kompiuterio programos nagrinėjimas ir nustatymas, ar programa veiks amžinai, ar ne. Sakome, kad programa "išsprendžia sustabdymo problemą", jei ji gali pažvelgti į bet kurią kitą programą ir pasakyti, ar ta kita programa veiks amžinai, ar ne.
Pavyzdžiui, tokia programa:
while True: tęsti;ciklas tęsis amžinai, tačiau programa
while False: tęsti;labai greitai sustoja.
Ar yra programa, kuri išsprendžia sustojimo problemą? Pasirodo, nėra. Šį faktą įrodysime parodydami, kad jei yra programa, kuri išsprendžia sustojimo problemą, tuomet įvyksta kažkas neįmanomo. Taigi kol kas elgsimės taip, tarsi programa, sprendžianti sustojimo problemą, tikrai egzistuoja. Čia P yra funkcija, kuri įvertins funkciją F (iškviestą su argumentu I) ir grąžins true, jei ji veikia amžinai, ir false priešingu atveju.
def P(F, I): if F(I) veikia amžinai: return True; else: return False;P gali peržiūrėti bet kurią programą ir sužinoti, ar ji veiks amžinai, ar ne. Naudodami P, sukursime naują programą, kurią pavadinsime Q. Q pažvelgia į kitą programą ir atsako į šį klausimą: "Jei paleisime šią programą ir priversime ją pažvelgti į savo kopiją, ar ji veiks amžinai?". Galime sukurti Q, nes turime P. Tereikia pasakyti Q, kad sukurtų naują programą, kuri būtų senoji programa, žiūrinti į save, ir tada panaudoti P, kad sužinotume, ar naujoji programa veiks amžinai, ar ne.
def Q(F): return P(F, F);Dabar sukuriame kitą programą R. R žiūri į kitą programą ir klausia Q atsakymo apie tą programą. Jei Q atsako "taip, jei paleisime šią programą ir priversime ją žiūrėti į savo kopiją, ji veiks amžinai", tada R sustoja. Jei Q atsako "ne, jei paleisime šią programą ir priversime ją žiūrėti į savo kopiją, ji neveiks amžinai", tada R patenka į begalinį ciklą ir veikia amžinai.
def R(F): if Q(F): return; //terminate else: while True: continue; //loop foreverDabar pažiūrėsime, kas nutiks, jei priversime R pažvelgti į savo paties kopiją. Gali nutikti du dalykai: jis arba sustos, arba veiks amžinai.
Jei paleidus programą R ir privertus ją žiūrėti į savo kopiją, ji neveikia amžinai, tuomet Q atsakė: "Taip, jei paleisime šią programą ir priversime ją žiūrėti į savo kopiją, ji veiks amžinai". Tačiau Q tai pasakė žiūrėdamas į pačią R. Taigi Q iš tikrųjų pasakė: "taip, jei paleisime programą R ir priversime ją žiūrėti į savo pačios kopiją, ji veiks amžinai". Taigi: Jei R, veikiantis savo paties kopijoje, neveikia amžinai, vadinasi, jis veikia amžinai. Tai neįmanoma.
Jei paleidus programą R ir privertus ją žiūrėti į savo kopiją, ji veiks amžinai, tuomet Q atsakė: "Ne, jei paleisime šią programą ir priversime ją žiūrėti į savo kopiją, ji neveiks amžinai". Tačiau Q tai pasakė žiūrėdamas į pačią R. Taigi iš tikrųjų Q pasakė: "ne, jei paleisime programą R ir priversime ją žiūrėti į savo pačios kopiją, ji neveiks amžinai". Taigi: Jei R, paleistas į savo paties kopiją, veikia amžinai, vadinasi, jis neveikia amžinai. Tai taip pat neįmanoma.
Kad ir kas nutiktų, susidaro nepavydėtina situacija. Padarėme kažką ne taip ir turime išsiaiškinti, kas tai buvo. Dauguma dalykų, kuriuos padarėme, nebuvo neteisingi. Negalime sakyti, kad "versti programą žiūrėti į savo kopiją yra neteisinga" arba "žiūrėti į tai, ką pasakė kita programa, ir pereiti į ciklą, jei ji pasakė vieną dalyką, ir sustoti, jei pasakė kitą dalyką", yra neteisinga. Nėra prasmės sakyti, kad mums neleidžiama daryti šių dalykų. Vienintelis dalykas, kurį padarėme ir kuris atrodo, kad galėtų būti neteisingas, yra tai, kad apsimetėme, jog tokia programa kaip P apskritai egzistuoja. O kadangi tai vienintelis dalykas, kuris galėtų būti neteisingas, ir kažkas turi būti neteisingas, tai jis ir yra neteisingas. Tai yra įrodymas, kad tokia programa kaip P neegzistuoja. Nėra programos, kuri išspręstų sustabdymo problemą.
Šį įrodymą 1936 m. rado Alanas Tiuringas.
Klausimai ir atsakymai
K: Kas yra Haltingo problema?
A: Haltingo problema yra informatikos problema, nagrinėjanti kompiuterio programą ir nustatanti, ar programa veiks amžinai, ar ne.
K: Kaip sužinoti, ar programa išsprendžia Haltingo problemą?
Atsakymas: Sakome, kad programa "sprendžia sustabdymo problemą", jei ji gali pažvelgti į bet kurią kitą programą ir pasakyti, ar ta kita programa veiks amžinai, ar ne.
K: Ar yra būdas įrodyti, kad tokios programos nėra?
A: Taip, parodant, kad jei tokia programa egzistuotų, įvyktų kažkas neįmanomo. Šį įrodymą 1936 m. rado Alanas Tiuringas (Alan Turing).
K: Ką daro P?
A: P yra funkcija, kuri įvertina kitą funkciją F (iškviestą su argumentu I) ir grąžina true, jei ji veikia amžinai, ir false priešingu atveju.
K: Ką daro Q?
A: Q nagrinėja kitą programą ir atsako į klausimą, ar paleidus tą pačią programą ant jos pačios, susidarys begalinė kilpa. Ji tai daro naudodama P, kad įvertintų duotąją funkciją F.
K: Ką daro R?
Atsakymas: R žiūri į kitą programą ir prašo Q atsakyti į klausimą apie tą konkrečią programą. Jei Q atsako "taip, jei paleisime šią programą ir priversime ją žiūrėti į savo kopiją, ji veiks amžinai", R sustoja; tačiau jei Q atsako "ne, jei paleisime šią programą ir priversime ją žiūrėti į savo kopiją, ji neveiks amžinai", R įeina į begalinį ciklą ir veikia amžinai.
Klausimas: Kas atsitinka, kai priverčiame R pažvelgti į save?
Atsakymas: Gali atsitikti du dalykai - arba R sustoja, arba veikia amžinai, tačiau abu rezultatai yra neįmanomi pagal tai, kas buvo įrodyta, kad tokios programos kaip P neegzistuoja, taigi kažkas kažkur pakeliui, kol privertėme R pažvelgti į save, turėjo būti negerai.
