Problém zastavenia

Problém zastavenia je problém v informatike. Problém spočíva v tom, že sa pozeráme na počítačový program a zisťujeme, či program bude bežať večne alebo nie. Hovoríme, že program "rieši problém zastavenia", ak sa dokáže pozrieť na akýkoľvek iný program a povedať, či tento iný program bude bežať večne alebo nie.

Napríklad takýto program:

while True: pokračovať;

sa bude opakovať donekonečna, ale program

while False: pokračovať;

sa veľmi rýchlo zastaví.

Existuje program, ktorý rieši problém zastavenia? Ukázalo sa, že nie je. Túto skutočnosť dokážeme tak, že ukážeme, že ak existuje program, ktorý rieši problém zastavenia, potom sa stane niečo nemožné. Preto sa zatiaľ budeme správať, akoby naozaj existoval program, ktorý rieši problém zastavenia. Tu je P funkcia, ktorá vyhodnotí funkciu F (volanú s argumentom I) a vráti true, ak beží večne, a false v opačnom prípade.

def P(F, I): if F(I) runs forever: return True; else: return False;

P sa môže pozrieť na akýkoľvek program a zistiť, či bude bežať večne alebo nie. Pomocou P vytvoríme nový program, ktorý nazveme Q. Q sa pozrie na iný program a potom odpovie na nasledujúcu otázku: "Ak spustíme tento program a prinútime ho pozrieť sa na kópiu seba samého, bude bežať navždy?". Môžeme vytvoriť Q, pretože máme P. Jediné, čo musíme urobiť, je povedať Q, aby vytvoril nový program, ktorý je starým programom pozerajúcim sa na seba samého, a potom pomocou P zistiť, či nový program pobeží navždy alebo nie.

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

Teraz vytvoríme ďalší program R. R sa pozerá na iný program a pýta sa Q na jeho odpoveď. Ak Q odpovie "áno, ak spustíme tento program a prinútime ho pozerať sa na kópiu seba samého, bude bežať večne", potom sa R zastaví. Ak Q odpovie "nie, ak spustíme tento program a prinútime ho pozrieť sa na kópiu seba samého, nebude bežať večne", potom R vstúpi do nekonečnej slučky a beží večne.

def R(F): if Q(F): return; //terminate else: while True: continue; //loop forever

Teraz sa pozrieme na to, čo sa stane, ak prinútime R pozrieť sa na kópiu seba samého. Môžu sa stať dve veci: buď sa zastaví, alebo bude bežať donekonečna.

Ak spustenie programu R a jeho pozeranie na kópiu seba samého neprebieha večne, potom Q odpovedal "áno, ak spustíme tento program a prinútime ho pozerať sa na kópiu seba samého, bude bežať večne". Ale Q to povedal, keď sa pozeral na samotný R. Takže Q v skutočnosti povedal: "áno, ak spustíme program R a prinútime ho pozerať sa na kópiu seba samého, bude bežať večne". Takže: Ak R beží na kópii seba samého, tak nebeží večne. To je nemožné.

Ak spustenie programu R a jeho pozeranie na kópiu seba samého trvá večne, potom Q odpovedal "nie, ak spustíme tento program a prinútime ho pozerať sa na kópiu seba samého, nebude trvať večne". Ale Q to povedal, keď sa pozeral na samotný R. Takže Q v skutočnosti povedal: "nie, ak spustíme program R a prinútime ho pozerať sa na kópiu seba samého, nebude bežať večne". Takže: Ak R beží na kópii seba samého, potom nebeží večne. To je tiež nemožné.

Bez ohľadu na to, čo sa stane, dostaneme sa do nemožnej situácie. Niečo sme urobili zle a musíme zistiť, čo to bolo. Väčšina vecí, ktoré sme urobili, neboli zlé. Nemôžeme povedať, že "urobiť program, ktorý sa pozerá na kópiu seba samého, je zlé", alebo "pozrieť sa na to, čo povedal iný program, a potom prejsť do slučky, ak povedal jednu vec, a zastaviť sa, ak povedal inú vec", je zlé. Nemá zmysel povedať, že tieto veci nesmieme robiť. Jediná vec, ktorú sme urobili a ktorá vyzerá, že by mohla byť nesprávna, je, že sme v prvom rade predstierali, že program ako P existuje. A keďže toto je jediná vec, ktorá by mohla byť nesprávna, a niečo nesprávne byť musí, je to práve toto. Toto je dôkaz, že program ako P neexistuje. Neexistuje program, ktorý by riešil problém zastavenia.

Tento dôkaz našiel Alan Turing v roku 1936.

Otázky a odpovede

Otázka: V čom spočíva problém Halting?

Odpoveď: Haltingov problém je problém v informatike, ktorý sa zaoberá počítačovým programom a určuje, či program bude bežať večne alebo nie.

Otázka: Ako zistíme, či program rieši problém zastavenia?

Odpoveď: Hovoríme, že program "rieši problém zastavenia", ak sa dokáže pozrieť na akýkoľvek iný program a povedať, či tento iný program bude bežať večne alebo nie.

Otázka: Dá sa nejako dokázať, že takýto program neexistuje?

Odpoveď: Áno, tak, že ukážeme, že ak by taký program existoval, potom by sa stalo niečo nemožné. Tento dôkaz našiel Alan Turing v roku 1936.

Otázka: Čo robí program P?

Odpoveď: P je funkcia, ktorá vyhodnocuje inú funkciu F (volanú s argumentom I) a vracia true, ak beží večne, a false v opačnom prípade.

Otázka: Čo robí Q?

Odpoveď: Q sa pozrie na iný program a potom odpovie na otázku, či spustenie toho istého programu na sebe samom povedie k nekonečnej slučke. Robí to tak, že pomocou P vykoná vyhodnotenie danej funkcie F.

Otázka: Čo robí R?

Odpoveď: R sa pozrie na iný program a spýta sa Q na odpoveď na tento konkrétny program. Ak Q odpovie "áno, ak spustíme tento program a prinútime ho pozerať sa na kópiu seba samého, bude bežať donekonečna", potom sa R zastaví; ak však Q odpovie "nie, ak spustíme tento program a prinútime ho pozerať sa na kópiu seba samého, nebude bežať donekonečna", potom R vstúpi do nekonečnej slučky a bude bežať donekonečna.

Otázka: Čo sa stane, keď prinútime R pozrieť sa na seba?

Odpoveď: Môžu sa stať dve veci - buď sa R zastaví, alebo pobeží donekonečna - ale oba výsledky sú nemožné podľa toho, čo bolo dokázané o neexistencii programov ako P, takže niekde na ceste vedúcej k tomu, aby sa R pozrel sám na seba, sa muselo niečo pokaziť.