Student World

***pravidelné páteční „přetištění“ staršího článku – tematické, vzhledem k tomu, že je právě Turingův rok

Aplikoval Turing diagonální metodu opravdu ve své ryzí podobě, při které se postuluje existence nekonečného objektu? Prostřednictvím postřehů přímo z originálního Turingova článku doplněnými vysvětlujícími komentáři se pokusíme ukázat, že Turing byl k diagonální metodě spíše skeptický. 

Tento rok /2006/ uplyne 70 let od zveřejnění slavného Turingova článku „On computable numbers, with an application to the entscheidungsproblem“.
Alanu Turingovi již bylo na ScienceWorldu věnováno hodně prostoru (např. http://www.scienceworld.cz/sw.nsf/ID/177488D16E6B4140C1256EAF0036FC02 a http://www.scienceworld.cz/sw.nsf/ID/A01CD9A7B6F2B564C1256E9700489B71). Jeho klíčový článek oceňujeme zejména proto, že v něm představil abstraktní výpočetní systém nazývaný dnes Turingův stroj (TM). Ukázalo se, že TM dobře vystihuje pojem algoritmu (počitatelnosti v intuitivním slova smyslu), ba dokonce, že je ekvivalentní všem jiným výpočetním systémům, které byly později navrhnuty ať už v abstraktní formě, či ve formě skutečných počítačů. Tzv. Churchova teze matematicko-filosofické povahy tvrdí, že všechny myslitelné výpočetní systémy jsou v tomto smyslu ekvivalentní (z hlediska toho co dokáží počítat). V závěru svého článku Turing s využitím získaných poznatků o TM dokazuje nerozhodnutelnost aritmetiky (entscheidungsproblem), což představuje zobecnění tehdy několik let starého Goedelova objevu neúplnosti aritmetiky (viz diskuse k článku http://www.scienceworld.cz/sw.nsf/ID/DB7DBF9EC58194D3C1256F0E004B34BC).

My se zde ovšem zaměříme na důkaz (prováděný diagonální metodou) faktu, že pro úlohu, zda se daný program po spuštění nikdy nezastaví a bude tisknout nekonečnou posloupnost znaků, či nikoliv, neexistuje obecný rozhodovací algoritmus. Jen pro přesnost poznamenejme, že tato rozhodovací úloha v Turingově originálním článku je mírně odlišná od dnes více popularizované úlohy zastavení, která spočívá v rozhodnutí, zda se daný program po spuštění někdy zastaví, či poběží věčně. Ne všechny TM, které se nikdy nezastaví, totiž počítají nekonečnou posloupnost znaků (jak požaduje v definici rozhodovací úlohy Turing) – některé se zacyklí a vygenerují pouze konečný počet znaků. Tento rozdíl v obou úlohách ale není z hlediska našich úvah podstatný – nadále se budeme držet Turingova výkladu.

Diagonální metoda byla již v ScienceWorldu podrobně pospána (http://www.scienceworld.cz/sw.nsf/ID/176FAFAA36CB3AB9C1256E970049211E a http://www.scienceworld.cz/sw.nsf/ID/003F237EB5967B0BC1256E970049211F). Připomeňme, že Cantor v 19. století v rámci jeho tzv. naivní (intuitivní, neformalizované) teorie množin ukázal, že množina reálných čísel má větší mohutnost než množina přirozených čísel (http://www.scienceworld.cz/sw.nsf/ID/E9B8D1DB935C34CCC1256E970048C62D), a též že existuje monumentální hierarchie navzájem různých nekonečných množin (kardinálních čísel), kterou později David Hilbert nazval rájem matematiků. I ve formální teorii množin, vybudované Zermelem a doplněné Fraenkelem na počátku minulého století, která odstranila nepříjemné paradoxy objevené v Cantorově světě množin a na které je postavena veškerá formální struktura současné matematiky, je díky vhodné volbě axiomů diagonální důkaz umožněn. Onen ráj tedy existuje dodnes a matematici v něm stále bádají. Diagonální metoda ovšem není pro lidskou intuici dokonale průhledná, neboť manipuluje s aktuálním (skutečně existujícím) nekonečnem. Samotná matice (tabulka), která se pro potřeby důkazu vytváří, je jen potencionálně nekonečná – v každém okamžiku máme k dispozici pouze konečnou matici, jsme však schopni ji neustále ve dvou směrech prodlužovat. Pak se ale pomocí prvků diagonály definuje nekonečný objekt, jemuž se přisoudí existence a se kterým se dále pracuje jako s aktuálním nekonečnem.

Aplikoval Turing diagonální metodu opravdu ve své ryzí podobě, při které se postuluje existence nekonečného objektu? Prostřednictvím postřehů přímo z originálního Turingova článku doplněnými vysvětlujícími komentáři se pokusíme ukázat, že Turing byl k diagonální metodě spíše skeptický. Turing si dává za úkol prozkoumat, která reálná čísla jsou počitatelná konečnými prostředky, to je na základě manipulace se symboly podle nějakého konečného souboru instrukcí, volně řečeno moderním jazykem, na základě počítačového programu. Proto definuje, jak již bylo řečeno, abstraktní výpočetní systém TM. Dále podrobně popisuje tzv. univerzální Turingův stroj (UTM), který je schopen po zadání patřičného popisu libovolného jiného TM na vstup, simulovat práci tohoto TM (to odpovídá dnešním možnostem programovat různé algoritmy v nějakém programovacím jazyce). Protože reálná čísla s nekonečným binárním rozvojem lze reprezentovat nekonečnými posloupnostmi nul a jedniček, zajímá se Turing právě o výpočet nekonečných posloupností nul a jedniček. Uvědomme si, že každá taková posloupnost je jen potencionálně nekonečný objekt. Člověk (pomocí příslušného TM) dokáže spočítat libovolný počet členů této posloupnosti, nikdy ji však neobsáhne jako celek. Turing si nejdříve představí – zdůrazněme, že zatím jde o představu – všechny odpovídající TM seřazené (očíslované přirozenými čísly) nějak takto:

TM(1) počítá 1001011 …..
TM(2) počítá 0111010 …..
TM(3) počítá 1001110 …..
TM(4) počítá 1101011 …..
TM(5) počítá 1101011 …..
atd.

Použití diagonální metody je v článku předvedeno jako drama o třech dějstvích. Na počátku je provokující úvaha:

1. Variace I – parodie na diagonální schéma

Turing píše:

Zdálo by se, že argument, který dokazuje, že množina reálných čísel není spočetná, též může dokázat, že množina počitatelných reálných čísel není spočetná…

Skutečně! Uplatníme-li totiž diagonální metodu tak, jak to provedl Cantor, můžeme definovat posloupnost P tak, že na jejím n-tém místě je 0 (resp. 1), je-li na n-tém místě posloupnosti počítaného strojem TM(n) 1 (resp. 0). V našem případě:

P = 00101….

Protože P je počitatelná posloupnost, počítá ji nějaký TM, řekněme TM(k). To ale vede ke sporu, neboť posloupnost počítaná TM(k) má na k-tém místě číslici jinou než posloupnost P. Množina počitatelných posloupností tedy není spočetná.

Na druhé straně je zřejmé, že každý TM je pospán konečně mnoha znaky z nějaké konečné abecedy. Všech TM (a tím spíše těch, které počítají nějakou nekonečnou posloupnost) je tedy spočetné množství. Co je špatně? Turing k tomu říká:

Chyba v argumentu spočívá v předpokladu, že posloupnost P je počitatelná. To by byla pravda, kdybychom uměli očíslovat počitatelné posloupnosti konečnými prostředky. Avšak problém očíslovat počitatelné posloupnosti je ekvivalentní rozhodovací úloze, zda TM s daným popisem počítá nekonečnou posloupnost. A my nemáme žádný obecný algoritmus, který by tuto úlohu rozhodoval v konečném počtu kroků.

Očíslováním zde Turning míní aplikaci nějakého algoritmu (tedy nějakého konkrétního TM), který by generoval popisy strojů TM(1), TM(2) atd., to znamená, realizoval by představu z tabulky výše. K tomu by stačilo mít k dispozici zmiňovaný obecný algoritmus, jak je zřejmé z následující úvahy: Předpokládejme, že existuje obecný algoritmus, který při libovolném vstupu po konečném počtu kroků oznámí, zda vstup je popisem nějakého TM, jenž počítá nekonečnou posloupnost, či nikoliv. Pak můžeme kombinací tohoto algoritmu a UTM sestavit speciální TM (ten, co Turing v uvedené citaci nazývá konečným prostředkem), který postupně probírá popisy všech možných TM (to lze provádět např. tak, že vezme nejdříve všechny popisy délky 1 znak, pak všechny popisy délky 2 znaky atd.) a každý popis vždy zkontroluje obecným algoritmem. Vytiskne pouze ty popisy, u nichž obecný algoritmus řekne ano – jde o popis TM počítajícího nějakou nekonečnou posloupnost. Tímto způsobem jsou postupně vytištěny popisy strojů: TM(1), TM(2), TM(3), a tedy i očíslovány všechny počitatelné posloupnosti.

2. Variace II – diagonální schéma po cantorsku – důkaz správný, leč podezřelý

Turing vysvětluje:

Ve skutečnosti, při správné aplikaci diagonální metody, můžeme ukázat, že žádný takový obecný algoritmus neexistuje. Nejjednodušší a nejpřímější důkaz je ukázat, že kdyby obecný algoritmus existoval, pak by existoval i TM, který počítá P. Tento důkaz, přestože je plně korektní, má nevýhodu, že by mohl u čtenáře vyvolat pocit, že „něco musí být špatně“.

Nejpřímějším důkazem Turing míní následující standardní (cantorovskou) aplikaci diagonálního schématu. Předpokládejme opět, že tento obecný algoritmus existuje. Pak můžeme, jak bylo výše vysvětleno, generovat jednotlivé stroje TM(1), TM(2), TM(3) atd. a vždy vytisknout 0, má-li posloupnost počítaná strojem TM(n) na n-tém místě 1, a vytisknout 0, má-li n-tém místě 1 (to znamená, že každý stroj spustíme a poté zastavíme v okamžiku, kdy se dopočteme hledaného členu). Tím počítáme posloupnost P. To je ale spor s tím , že P je nepočitatelná. Obecný algoritmus tedy neexistuje.
Turning je skeptický k takto „správně použité“ diagonální metodě proto, že se při její aplikaci předpokládá existence nějakého nekonečného objektu – nepočitatelné posloupnosti P. Jaký důkaz, nevyvolávající pocit, že „něco musí být špatně“, tedy Turing nabízí?

3. Variace III– diagonální schéma s konečnou diagonálou

Turing pokračuje:

Důkaz, který podám, tuto nevýhodu nemá ….. Spočívá nikoliv v konstrukci P, nýbrž v konstrukci posloupnosti Q, jejíž n-tý člen je roven n-tému členu posloupnosti počítané strojem TM(n).

Idea důkazu, který Turing považuje za správný, je následující. Předpokládejme (do třetice), že existuje obecný algoritmus, který při libovolném vstupu po konečném počtu kroků oznámí, zda vstup je popisem nějakého TM, jenž počítá nekonečnou posloupnost, či nikoliv. Úplně stejně jako při variantě II sestavíme kombinací tohoto obecného algoritmu a UTM speciální TM, který spouští a zastavuje postupně TM(1), TM(2), TM(3) atd. Na rozdíl od variace II ovšem tiskne první člen posloupnosti počítané TM(1), druhý člen posloupnosti počítané TM(2), atd. Neusiluje tedy o výpočet něčeho aktuálně nekonečného a nepočitatelného.

Tento speciální TM byl zkonstruován tedy tak, že počítá potenciálně (!) nekonečnou posloupnost (tj. tiskne stále nová a nová čísla). Jedná se tedy o stroj TM(k) pro nějaký index k. Co se ovšem stane až tento stroj TM(k) narazí na svůj vlastní popis? Obecný algoritmus mu sdělí, že TM(k) počítá nekonečnou posloupnost a že je ho třeba spustit. To se opakuje, TM(k) proto začne rekurzivně volat sám sebe. Výpočet se zacyklí a nikdy se nedopočítá k-tého členu posloupnosti počítané TM(k). To je spor s tím, že TM(k) počítá nekonečnou posloupnost. Pro ilustraci, je-li např. k=3, lze použitou diagonální metodu znázornit takto (všimněme si konečné diagonály):

TM(1) počítá 1001011 …..
TM(2) počítá 0111010 …..
TM(3) počítá 1001110 …..
TM(4) počítá 1101011 …..
TM(5) počítá 1101011 …..
atd.

Rozdíl mezi Variací II a Variací III je delikátní. V případě Variace II se konstruuje nekonečná nepočitatelná posloupnost P a poté se s ní zachází jako s existujícím objektem (aktuálním nekonečnem) – snažíme se tento objekt počítat. V rámci Variace III se vlastně žádná nekonečná posloupnost nedefinuje, jen se sestaví speciální TM jako konečný objekt. Pak ukáže se, že ke sporu dochází už po konečném počtu kroků výpočtu (viz tabulka), totiž v okamžiku, kdy tento TM začne zkoumat sám sebe. Na zacyklení přitom není nic záhadného, neboť jde v podstatě o rekurzivní volání podprogramu, což dnes umožňují některé programovací jazyky. V pozadí se vznáší jen konečná diagonála – spor byl usazen do konečného horizontu v zorném poli člověka.
To, že se Turing drží argumentace bez použití aktuálního nekonečna je zcela v duchu jeho článku – vždyť zkoumá právě to, co člověk dokáže generovat konečnými prostředky. Všechny posloupnosti, které je člověk schopen generovat, byť s použitím počítače, jsou pouze potencionálně nekonečné. Existence aktuálního nekonečna i celého ráje množin vybudovaného Cantorem bude navždy spekulativní a je ji třeba považovat za otázku víry. Vždyť i asi nejsilnější argument pro existenci aktuálního nekonečna – argument Bolzanův – je teologické povahy (http://www.scienceworld.cz/sw.nsf/ID/A9D1AA80B683BBF4C1257004006FA945). Turing tak projevil opatrnost při použití diagonální metody a odolal svádění ďábla zamaskovaného v podobě aktuálního nekonečna v klasické Cantorově diagonální metodě.

autor Otto Huřťák