Student World

pravidelné páteční „přetištění“ staršího článku

Jak zkonstruovat program, který vytiskne sám sebe? Tato úloha patří k oblíbené zábavě programátorů, přičemž existuje v řadě modifikací (např. najít nejkratší program, který vytiskne sám sebe, a dokázat, že je opravdu nejkratší).
Programem, který tiskne sám sebe, samozřejmě nemyslíme program obsahující příkaz k otevření souboru se svým zdrojovým kódem a jeho vytištění. I „regulérní“ řešení může mít ovšem celou řadu podob, v první řadě podle zvoleného jazyka. Přehled různých „quines“ (jak se programy tisknoucí samy sebe samé, self-printing programs, nazývají – dle amerického analytického filozofa a logika Quinea) najdete např. na stránce http://www.nyx.net/~gthompso/quine.htm.
Pro ty nás, kteří se programováním ve větší míře setkali jen v podobě různých Basiců a Pascalů, nemá asi příliš smysl studovat zdrojáky v Tcl či Prologu. Třeba programy v Pascalu uvedené na http://www.nyx.net/~gthompso/self_pasc.txt jsou ovšem ilustrativní a pochopitelné.

Například

const a=’const a=';b=’begin write(a,#39,a,#39#59#98#61#39,b,#39#59#10,b) end.';
begin write(a,#39,a,#39#59#98#61#39,b,#39#59#10,b) end.

V této souvislosti ještě několik otázek. Pokud budete hovořit s lidmi, kteří se problémem nezabývali, budou vesměs přesvědčeni, takový program vůbec nelze sestrojit. Jak byste nejnázorněji vysvětlili princip programu?
V logice je autoreference jedním ze zdrojů paradoxů. Od problému lháře k problému zastavení, kde necháte algoritmus, aby se zadávil právě sám sebou, se tímto způsobem obvykle dokazuje, že „něco nejde“. Nepřijde vám v tomto světle fakt, že program tisknoucí sám sebe vůbec existuje, trochu zvláštní, jako by byl v rozporu s tím, že žádný systém nemůžete uchopit z jeho vnitřku?
(Jedna z možných odpovědí: Paradoxy, problém zastavení či Goedelova věta ukazují, že existují věci nějak zvláštní, výroky podivné, situace, které algoritmy nedokáží apod… Neříkají ale rozhodně nic o tom, že všechny objekty jsou takhle zvláštní – tj. program tisknoucí sám sebe prostě patří do skupiny těch neproblematických a normálních programů, které dokáží udělat to, co udělat mají.)

autor Pavel Houser