Halting problem

Už od 30. let minulého století se ví, že existují problémy, které se nedají algoritmicky rozhodnout (vyřešit). Pokusím se tady srozumitelnou cestou ukázat, že takový neřešitelný problém existuje. Je to taková pěkná zajímavost z teoretické informatiky a pochopí ji snad každý laik.

Jedná se o notoricky známý Halting problem.
Jak asi kdokoliv, kdo někdy používal počítač, ví, v mnoha programech se vyskytují chyby, jež způsobí, že program například přestane reagovat na uživatelovy instrukce, něco neúměrně dlouho provádí, prostě se “zasekne”.
Představte si, že někdo řekne “neexistuje testovací program, který spolehlivě zjišťuje, zda se nějaký jiný vybraný program zasekne (nikdy nezastaví), nebo doběhne do konce (zastaví)”.

Pokud by někdo tvrdil, že takový program vyrobil, tak ukážu, že nefunguje. Nazvěme takový program Zkoušeč. Napíšu nový program, nazvěme ho Popírač. Program Popírač dělá následující:
Spusť program Zkoušeč, aby zanalyzoval program Popírač.
Pokud výsledek Zkoušeče byl “Popírač se zasekne”, skonči.
Pokud výsledek Zkoušeče byl “Popírač se nezasekne”, vstup do nekonečné smyčky (zasekni se).

Když spustím tento program Popírač a on nedoběhne (zasekne se), znamená to, že Zkoušeč hlásil “nezasekne” (anebo se zaseknul sám Zkoušeč).
Pokud program doběhne, znamená to, že Zkoušeč zahlásil “zasekne se”.

Takže program se nazaseknul v případě, kdy Zkoušeč zjistil, že se měl zaseknout. Anebo se zaseknul v případě, kdy Zkoušeč zjistil, že se zaseknout neměl. Program Zkoušeč zjevně nefunguje, jak má.

Takže program, který by měl zjistit, zda nějaký jiný program správně doběhne nebo ne, neexistuje. Pokud by někdo tvrdil, že existuje, výše uvedeným postupem se ukáže, že nefunguje.
Problém zjištění, zda nějaký program doběhne do konce nebo se zasekne, je tak nerozhodnutelný (algoritmicky neřešitelný) problém.

3 thoughts on “Halting problem

  1. Hezky vysvetleno, to musi pochopit i student VUT.

    Minuly tyden nam to vykladal kdosi v inteligentnich systemech, ale dokazoval to na trochu jinem prikladu, mel jenom jeden program a ten v obdobnem duchu kontroloval sam sebe.

    To mi pripomina, jak jsme tuhle, jeste na gymplu, sli spolu domu a ty jsi mi o tomhle problemu rikal. Tenkrat jsi mi ho nedokazal moc vysvetlit a ja ho nebyl sto pochopit.

    Inu, casy se meni :).

  2. ty vole kamo, možná to je tou horečkou, ale mám dojem, že to je asi nějaký dadaistický příspěvek. no nic, jdu do dalšího paralenu

Comments are closed.