Řešení neřešitelného

V krátkosti se seznámíme s důvody, proč poslední půlhodinu upadám v nekontrolovatelné výbhuchy smíchu, padám ze židle a válím se pod stolem.

Za všechno může jistá D. D., která dovolila Ondřeji Holečkovi zveřejnit na root.cz tento článek: Co je to nenaprogramovatelné? Publikováno už v listopadu 2003, ale dostal jsem se k tomu až nyní díky všímavosti BST.

Holeček v článku vysvětluje problém zastavení (existuje program, který by o libovolném jiném programu rozhodl, zda se zastaví?), který je úvodem k tzv. vyčíslitelnosti (ve které se řeší, co všechno lze vyčíslit, co ne, a proč ne, a kdyby jo, tak proč něco jiného ne, a dospívá k tomu, že vždycky něco ne).

A k článku se rozvinula poměrně veselá diskuse. Všichni si (více či méně úspěšně) oprášili své akademické znalosti a seznámili s nimi široké okolí. Začíná to vcelku nevinně: že je to fáma, že je to v praxi stejně jedno a tak podobně.

Ale pak se objeví Milan Šorm a napíše: "Mne to teda vyčíslitelnost nepřipomíná. Když už tak složitost (redukce všech problémů na problém zastavení, který nelze řešit a proto mají všechny uvedené úlohy stejnou složitost NP), ale spíš docela obyčejné formální jazyka a gramatiky typu 0 v Chomského hierarchii."

Nesmějete se? Tak mám pro alternativu: Upekli jste bábovku a někdo prohlásí: Mně to teda bábovku nepřipomíná. Když už tak nábytek (když se někam dává oblečení, tak je to dřevěné, a proto má každá skříňka světýlko), ale spíš docela obyčejné knížky a časopisy. Smysl je velmi podobný.

Nu dobrá, třeba je Šorm nějaký prosťáček, který mele páté přes deváté. Skoro - Mgr. Ing. Milan Šorm, čtyřnásobný Microsoft Certified Professional, odborný asistent Ústavu informatiky PEF MZLU v Brně, učí předmět Vybrané otázky teoretické informatiky I! No tedy, to ty otázky musí být setsakra dobře vybrané...

A do toho už přicházejí další ohlasy: Přiznávám se bez mučení, že mi to celé připadá jako blábol a že funkci zastavi bych určitě naprogramoval a to dokonce na 3-4 řádky, ale možná jsem jenom nepochopil co tím chtěl básník říci (čili uznávám vlastní blbost ;)).

To je radost, setkávat se s takovými přímočarými programátory. A jako perlička večera se objeví Zdeněk Pavlas, který navzdory celému světu problém zastavení vyřešil, neboť "je to triviální". A hned dodává: "Vazne nevim co ti vedatori resi." A: "Program který nelze spustit nemá smysl analyzovat, nemyslíte? Jde o teoretický konstrukt (čti výmysl) a přemýšlet nad ním je zhruba stejně zbytečné jako soutěž v čurání do dálky." A pak, že všechno jde, a nejdůležitější otázka je, zda se počítá ve floatech nebo v doublech (což my, programující stěží v celých číslech, sotva oceníme).

A pak už se radostně přidávají další. Toto je též pikantní: "Nechcete zacit delat neco uzitecneho? Kopat prikopy nebo tak neco ? imho fce pro zjisteni zda program dojde do konce nebo ne napsat lze. Pouze predvadena konstrukce zpusobi zacykleni. Stejne tak by se dalo zacyklit hodne veci. Ale to preci neznamena ze nejdou napsat!!! [...] Pro me je totiz dukaz neco ve tvaru 5=5 a ne nejakej zacyklenej haluz."

Pak už se to jenom zvrhne do toho, jestli hulit víc nebo míň trávy, do toho už tak moc nevidím. Závěrečná poznámka v diskusi ale svádí ke skutečnému zamyšlení: Proč testujeme na zastavení sami sebe? Ano, ptám se já, proč? Zastavme se a rozjímejme...