Toto je sedmý díl seriálu o logice, který volně sleduje myšlenky D.Hofstadtera sepsané v jeho knize Gödel, Escher, Bach. Navigace: úvodní článek - předchozí díl - příští díl.
Minule jsme si zběžně představili formální verzi aritmetiky; systém, ve kterém řetězce symbolů, jako třeba SS0=(S0+S0) nebo ∃n:(SSS0+n)=0, odpovídají výrokům z teorie čísel, jako třeba „jedna plus jedna je rovno dvěma“ nebo „tři je menší než nula“. Zajímavá a důležitá otázka je, jaké všechny výroky je možno formulovat pomocí řetězců tohoto systému. Pro (částečnou) odpověď se hodí definovat třídu funkcí, které se nazývají primitivně rekurzivní.
Mluvím-li v tomto článku o funkcích, mám na mysli takové, jejichž argumenty i návratové hodnoty jsou přirozená čísla (včetně nuly). Speciálním příkladem jsou pak predikáty, které mohou vracet pouze dvě hodnoty interpretované jako „pravda“ a „nepravda“ (standardně lze zvolit 1 a 0). Primitivně rekurzivní funkce tvoří podmnožinu všech funkcí a existuje několik ekvivalentních definic, které tuto podmnožinu definují. Intuitivně nejsrozumitelnější se zdá definice pomocí algoritmů, kterými je možné funkce vyčíslit: primitivně rekurzivní funkce jsou všechny takové, které lze spočítat pomocí programu obsahujícího pouze „primitivní operace“ a omezené cykly.
Primitivní operace jsou takové, které mají v daném programovacím jazyku předdefinované symboly nebo klíčová slova. Jaké operace se považují za primitivní je definováno výčtem; v podstatě se jedná o definici programovacího jazyka užitého pro vymezení primitivně rekurzivních funkcí. Jeho přesná podoba není až tak podstatná, protože různé volby mohou snadno vést ke stejné množině primitivně rekurzivních funkcí — stejný program lze zpravidla naprogramovat v různých programovacích jazycích. Pro konkrétnost lze za primitivní považovat sčítání, násobení a porovnávání čísel a přiřazování hodnot do proměnných. Dále musí být k dispozici instrukce, která zamezí vykonání části kódu, není-li splněna určitá podmínka (ve většině programovacích jazyků se taková instrukce nazývá if).
Klíčovou částí definice primitivně rekurzivních funkcí je existence pouze omezených cyklů. Omezený cyklus je část kódu, která se vykonává opakovaně; omezenost znamená, že před započetím cyklu je známý maximální počet opakování a tento počet je konečný. Ve většině programovacích jazyků odpovídá omezeným cyklům instrukce for. V následujícím textu budu využívat syntaxi jazyka Pascal, ve zjednodušené podobě: nesmím používat operátory dělení nebo odčítání (nejsou primitivní operace), proměnné jsou všechny přirozená čísla bez omezení maximální velikosti (a není tak třeba je deklarovat), a hlavně: jediný povolená instrukce navazující cyklus je for. Potenciálně neomezené cykly repeat a while, stejně jako instrukce goto, kterou tyto cykly lze nahradit, jsou zakázány. Absence neomezených cyklů zaručuje, že jakýkoli program napsaný v tomto jazyce skončí — nedostane se do nekonečné smyčky, ani například nebude zkoušet jedno přirozené číslo za druhým, zda nemá určitou vlastnost, bez jistoty, že vůbec nějaké číslo s tou vlastností existuje. Primitivně rekurzivní funkci lze spočíst v konečném čase pro každou možnou hodnotu jejích parametrů. (To ovšem neznamená, že jakákoli funkce, jejíž hodnoty spočítá terminující program, je primitivně rekurzivní.)
Příkladem primitivně rekurzivních funkcí jsou mocniny. Například, funkci xy můžeme naprogramovat takto:
function mocnina(x,y);
begin
z:=1;
for i:=1 to y do z:=z*y;
mocnina:=z;
end;
Funkce mocnina obsahuje jeden cyklus, který proběhne právě y-krát. Čím větší y, tím déle program poběží, ale vždy skončí po konečném množství operací.
Cyklus může být přerušen, je-li splněna určitá podmínka. Například funkce, která určuje, zda n je prvočíslo (vrací 1 pokud ano, 0 pokud ne):
function prvocislo(n);
begin
z:=1;
for i:=2 to n-1 do
for j:=2 to i do
if i*j=n then
begin z:=0; break; end;
prvocislo:=z;
end;
Funkce prohledává všechny možné dvojice dělitelů čísla n, a jakmile nějakou najde, ukončí další hledání (instrukcí break) a vrátí negativní odpověď. Dvojice vnořených cyklů projde všechny hodnoty pouze pokud je hledání neúspěšné a n je prvočíslem.
Funkce prvocislo je příkladem primitivně rekurzivního predikátu. Jejím parametrem je přirozené číslo a návratová hodnota má interpretaci pravda nebo nepravda. Podstatné tvrzení je, že všechny primitivně rekurzivní predikáty lze vyjádřit jako řetězce formální aritmetiky. Toto tvrzení bude pravděpodobně nejslaběji podloženým tvrzením v celé sérii článků, poněvadž mi není známo, jak se dokazuje. (Hofstadter tento problém elegantně ignoruje.) Na jedné straně se zdá přirozené, že má-li být formální aritmetika co k čemu, musí být schopna nejen vyjádřit, ale i dokázat tvrzení typu „n je prvočíslo“, obecněji pak všechna tvrzení, jejichž pravdivost jsme schopni otestovat pomocí zaručeně terminujícího algoritmu. Na druhé straně jsme minule viděli, že i velmi jednoduchý primitivně rekursivní fakt „n je mocnina dvou“ je vyjádřen velmi nepřímočarým způsobem pomocí prvočíselných dělitelů; jen o trochu složitější predikáty, jako například „n je mocnina šesti“, natož „n je mocnina nějakého přirozeného čísla“, jsou ještě o několik stupňů těžší (můžete se pokusit tyto predikáty formalizovat, ovšem nepočítejte s úspěchem). Každopádně požádám čtenáře, aby přijali vyjádřitelnost primitivně rekurzivních predikátů jako fakt, a pokročím dále.
Zatím jsme viděli příklady funkcí, které byly primitivně rekurzivní. Zajímavá otázka je, zda existují funkce, které nejsou primitivně rekurzivní. Kladnou odpověď dává slavný Cantorův diagonální argument. Cantor původně použil tento argument pro důkaz, že množina reálných čísel je nespočetná, tj. že nelze napsat posloupnost reálných čísel, ve které by bylo každé reálné číslo zastoupeno. Argument ve své původní podobě vypadá následovně: Předpokládejme, že můžeme reálná čísla seřadit do posloupnosti. Potom lze jistě seřadit do posloupnosti reálná čísla z intervalu <0,1) — bude to podposloupnost posloupnosti všech reálných čísel. Sepišme tedy pod sebe desetinné rozvoje těchto čísel tak, jak následují v posloupnosti. Dostaneme tak nekonečnou tabulku, jejíž prvních několik řádků bude vypadat třeba nějak takhle:
Podle předpokladu tabulka obsahuje všechna reálná čísla. Nadefinujeme nyní číslo D tak, že jeho desetinný rozvoj tvoří číslice vzniklé z číslic na diagonále této tabulky (jsou vyznačeny tučně) přičtením 1 ke každé (pokud je na diagonále 9, na odpovídajícím místě rozvoje D je 0). Pro naši ilustrační tabulku vyjde D = 0,39383065... Takto zkonstruované D je jistě reálné číslo ležící v daném intervalu, které se nikde v tabulce nenachází, protože jeho konstrukce zaručuje, že se od čísla na k. řádku liší přinejmenším číslicí na k. pozici desetinného rozvoje. To je ale ve sporu s předpokladem, že v tabulce jsou všechna reálná čísla, a protože argument nezávisí na tom, jak posloupnost reálných čísel konkrétně vypadá, plyne z toho, že reálná čísla nelze všechna seřadit do posloupnosti.
Aplikace diagonálního argumentu pro důkaz existence funkcí, jež nejsou primitivně rekurzivní, probíhá opačným směrem. Zde víme, že primitivně rekurzivní funkce lze uspořádat do posloupnosti. Učiníme to třeba tak, že vezmeme všechny syntakticky správné programy definující nějakou funkci a uspořádáme je nejdříve podle počtu znaků. Uvnitř každé ze skupin programů o stejném počtu znaků (kadžá taková skupina obsahuje pouze konečné množství programů) pak programy uspořádáme abecedně. Nyní můžeme každému programu přiřadit jednoznačně jeho číslo: ve skupině nejkratších programů bude programu na n. místě abecedního pořadí přiřazeno číslo n, ve druhé nejkratší skupině program na n. místě abecedního pořadí dostane číslo n + p, kde p je počet programů v první skupině atd. Každý program definuje nějakou primitivně rekurzivní funkci (různé programy mohou definovat stejnou funkci, ale to nevadí) a funkci definovanou n. programem označíme fn. Následně si vytvoříme tabulku, kde v n. řádku a k. sloupci bude hodnota fn(k). Tabulka bude vypadat nějak takto [1]:
Nadefinujeme teď funkci D(n) takto: D(n) = fn(n) + 1, tj. její hodnoty získáme z čísel ležících na diagonále tabulky. Funkce D je různá od libovolné funkce fn. Jelikož ale víme, že posloupnost funkcí fn obsahuje všechny primitivně rekurzivní funkce, funkce D nemůže být primitivně rekurzivní.
Fakt, že ne všechny funkce jsou primitivně rekurzivní, je možná zajímavý sám o sobě. Je zároveň i překážkou v naší snaze o konstrukci formálního výrazu, který bude přes Gödelovo číslování ekvivalentní lhářovu paradoxu. Připomenu z minula, že chceme, aby výraz o svém vlastním Gödelově čísle tvrdil, že to není Gödelovo číslo teorému; tímto způsobem výraz mluví o své nedokazatelnosti. Tvrzení T(n) = „číslo n není Gödelovým číslem teorému“ je predikát s jedním číselným parametrem. Kdyby T(n) byl primitivně rekurzivní predikát, měli bychom jistotu, že jej lze vyjádřit jako řetězec formální aritmetiky. Kdyby ale T(n) bylo primitivně rekurzivní, existoval by terminující algoritmus, který by umožňoval pro libovolné číslo ověřit, zda je Gödelovým číslem teorému, a tudíž pro libovolný výraz ověřit, zda je teorémem. Kdyby tomu tak bylo, bylo by dokazování matematických vět triviálně mechanickou činností a matematikové by přišli o práci [*]. Realita je ovšem komplikovanější: žádný mechanický postup pro ověření, zda výrok je dokazatelný, nemáme. Je proto odůvodněné se domnívat, že T(n) není primitivně rekurzivní.
Naštěstí se nabízí laciná cesta ven z tohoto problému, přes zavedení Gödelova číslování nejen pro výrazy, ale pro celé jejich sekvence vyjadřující důkazy. Udělat se to dá zcela analogicky číslování teorémů: každému znaku z formální abecedy se přiřadí jednoznačná sekvence číslic a sekvence se slepí k sobě. Navíc potřebujeme akorát číselnou kombinaci pro konec řádku. Uvažme kupříkladu odvození
- ((S0=S0+0)⇒(0+S0=S0))
- (S0=S0+0)
- (0+S0=S0)
Zvolme libovolné Gödelovo číslování, například ( ~ 1, ) ~ 2, S ~ 3, 0 ~ 4, = ~ 5, + ~ 6, ⇒ ~ 7 a konec řádky ~ 8. Odvození můžeme zapsat jako ne zrovna malé číslo 113 453 464 271 463 453 422 813 453 464 281 463 453 428.
Jakmile máme očíslované důkazy i teorémy, můžeme zavést predikátovou funkci P(m,n), která vrací hodnotu pravda právě tehdy, když m je Gödelovým číslem odvození výrazu s Gödelovým číslem n. Tvrzení, že uvedené odvození je důkazem výroku „nula plus jedna je rovno jedné“ stojícího na poslední řádce, je pravdivé právě tehdy když P(113 453 464 271 463 453 422 813 453 464 281 463 453 428, 146 345 342) = pravda. (V tomto konkrétním případě bude ovšem predikát P nepravdivý, protože ač třetí řádek z prvních dvou plyne přes modus ponens a první dva řádky jsou teorémy, chybí jejich odvození. Aby P vracelo hodnotu pravda, je nutné, aby odvození bylo úplné: tj. všechny neodvozené řádky musejí být axiomy.)
Na rozdíl od funkce T(n) je funkce P(m,n) primitivně rekurzivní: zatímco zjistit, zda určitý výraz je teorém znamená povinnost hledat důkaz bez jistoty úspěchu, zjistit, zda předložené odvození je korektní je skutečně mechanická operace: postupujeme odvozením řádek po řádku a pro každý zjišťujeme, zda vyplývá z nějakých výše uvedených řádků pomocí legálního odvozovacího pravidla. Jelikož je řádků i pravidel konečný počet, lze s pomocí pouze konečných cyklů stvořit program, který bude tuto činnost vykonávat.
Primitivní rekurzivita funkce P implikuje, že existuje výraz, jehož interpretace je právě predikát P(m,n). Program ověřující korektnost odvození teorémů pochopitelně zabere víc než jen pár řádek, jeho reformulace do formálního jazyka s využitím Gödelova číslování tak bude představovat obludně dlouhý výraz. I kdybych explicitní podobu tohoto výrazu znal a chtěl ho vypsat explicitně, zabralo by to stovky nebo možná tisíce blogových článků. Protože mě ale na tomto výrazu zajímá pouze to, že existuje, spokojím se se zkratkou P(m,n) [*].
Nyní přichází pro dnešek poslední krok, a to konstrukce výrazu, který má interpretaci „n je Gödelovo číslo teorému“. Řekli jsme si, že ověřování toho, zda je n G.č. teorému není primitivně rekurzivní proces, a tak nemáme automaticky zajištěno, že tento predikát bude možno vyjádřit formálně. Můžeme si ale snadno pomoct primitivně rekurzivním predikátem P: výraz ∃m:P(m,n) má interpretaci „existuje číslo m, které je G.č. korektního odvození výrazu, jehož G.č. je n“; krátce „existuje důkaz pro výraz s G.č. n“, neboli „výraz s G.č. n je teorém“.
Poslední problém, který zbývá na příště, je jak nacpat dovnitř výrazu jeho vlastní Gödelovo číslo.
Poznámky:
1.Přísně vzato tabulka neodpovídá řazení programů podle délky zápisu v našem modifikovaném Pascalu; nejkratší program korektně zapsaný v této syntaxi je
function a(b);
begin
a:=0;
end;
reprezentující konstantní nulovou funkci. Nicméně naše řazení není jediné možné řazená programů a náš jazyk není jediný možný jazyk, lze si tak představit i jiné řazení produkující naši ilustrační tabulku.
Žádné komentáře:
Okomentovat