1. M-MÓD, I-MÓD, U-MÓD
  2. Rozhodovací procedury
    1. 2. Dvojhlasá invence

M-MÓD, I-MÓD, U-MÓD

Zadání Problému MU bylo formulováno tak, aby mírně povzbudilo průzkum odvozování teorémů, tedy práci uvnitř MIU-systému, na druhé straně však nic v zadání nenaznačuje, že bude nezbytně prospěšné uvnitř systému setrvávat. Účelem bylo povzbudit jistou oscilaci mezi oběma způsoby práce. Jedna možnost, jak tyto způsoby od sebe oddělit, je vzít dva listy papíru a na jednom papíru pracovat „strojovou metodou“ — zaplňovat ho písmeny M, I, U — zatímco na druhém listu uplatnit „schopnosti myslící bytosti“ jakýmkoli způsobem, který nám naše inteligence napoví. To může zahrnovat užití přirozeného jazyka, náčrty, zpětnou analýzu, využití zkratek (např. písmene „x“), slučování několika kroků do jednoho, sledování vlivu změny pravidel na chování systému — prostě cokoli, co nás napadne. Mezi tyto možnosti zkoumání patří i postřeh, že v systému hrají důležitou roli čísla 2 a 3, protože se můžeme zbavit trojic I, dvojic U a díky pravidlu II také zdvojnásobit délku řetězce (počítanou bez počátečního M). Na druhém listu se tak mohou objevit i nějaká čísla. K oběma těmto způsobům nakládání s formálními systémy se budeme občas vracet, budeme je nazývat mechanický mód (M-mód) a inteligentní mód (I-mód). Abychom doplnili uvedené módy i o třetí písmeno MIU-systému, zavedu ještě únikový mód (U-mód), který odpovídá zenovému vztahu k věcem. O tom ale více v dalších kapitolách.

Rozhodovací procedury

Jedním z poznatků o našem hlavolamu je, že zahrnuje pravidla dvou navzájem opačných tendencí — prodlužování a zkracování. Dvě pravidla (I a II) umožňují zvětšit délku řetězce (samozřejmě jen předepsaným způsobem) a další dvě dovolují řetězce o něco zkrátit (opět jen daným způsobem). Zdá se, že je nekonečně mnoho možností, jak tato pravidla postupně používat, což vzbuzuje naději, že MU lze nakonec nějakým způsobem získat. Možná by šlo prodloužit řetězec na nějakou ohromnou délku a pak odebírat písmenko po písmenku, až zůstanou jen potřebná dvě. Ještě zoufalejší metoda by mohla zahrnovat střídavé prodlužování a zase zkracování — nic nám však neposkytuje žádnou záruku zdárného konce. Koneckonců už jsme zjistii, že U nedokážeme vytvořit nikdy, i kdybychom prodlužovali a zkracovali až na věčnost.

Nicméně případy U a MU jsou zjevně naprosto rozdílné. Díky dost triviální vlastnosti U je zřejmé, že ho nelze vytvořit: nezačíná totiž na M, což všechny teorémy musí. Je velice příjemné, že existuje takový jednoduchý způsob, jak poznat, co není teorémem. Kde je však psáno, že takto odhalíme všechny ne-teorémy? Může existovat mnoho jiných řetězců, které na M začínají, ale nelze je vytvořit. Možná je MU jedním z nich. To by znamenalo, že „test na první písmeno“ má svá omezení, protože umožňuje odhalit jen část ne-teorémů, zatímco jiné projdou. Stále nám však zůstává otevřena možnost, že existuje nějaký důmyslnější test, jenž by dokonale roztřídil řetězce na ty, jež lze pravidly vytvořit, a na ty, jež vytvořit nelze. Stojíme tu před otázkou: „Co rozumíme testem?“ Asi není zřejmé, zda má v tomto kontextu taková otázka smysl ani proč by měla být důležitá. Proto se podívejme na příklad „testu“, který svým způsobem porušuje ducha toho slova.

Představme si džina, který má k dispozici veškerý čas na světě a který ho užívá metodickým vytvářením teorémů MIU-systému. Zde je jedna možnost, jak by si mohl džin počínat:

1. krok: Uplatni všechna použitelná pravidla na axiom MI. To dává dvě nové věty: MIU, MII.

2. krok: Uplatni všechna použitelná pravidla na věty vytvořené v 1. kroku. To dává tři nové věty: MIIU, MIUIU, MIIII.

3. krok: Uplatní všechna použitelná pravidla na věty vytvořené v 2. kroku. To dává šest nových vět: MIUIUIUIU, MIIUIIU, MIIIIU, MIIIIIIII, MUI, MIU.

Touto metodou džin vytvoří dříve či později každou větu, protože pravidla jsou používána všemi představitelnými způsoby (obr. 11). Všechny možnosti postupného prodlužování a zkracování, jež jsme zmiňovali výše, se tu někde vyskytnou. Není však jasné, jak dlouho budeme muset čekat, než se daný řetězec na tomto seznamu objeví, protože teorémy jsou řazeny podle délky jejich odvození. To není příliš užitečné pořadí, pokud vás zajímá jen určitý řetězec (takový jako MU), o němž navíc ani nevíte, zda vůbec nějaké odvození má, natož jak dlouhé může být.

A nyní slíbený „test“, zda je řetězec teorémem, čili jeho „teorémovosti“:

Čekejte, dokud se požadovaný řetězec neobjeví; jakmile se objeví, víte, že jde o teorém, a pokud se nikdy neobjeví, víte, že to teorém není.

Obr.11 Systematicky sestavený „strom“ všech vět MIU systému. N-tá úroveň od shora obsahuje všechny věty, k jejichž odvození bylo potřeba právě N kroků. Čísla v kroužcích uvádějí, které pravidlo bylo použito. Je MU někde na tomto stromě?

To zní absurdně: předpokládá se, že nám nevadí čekat na odpověď doslova nekonečně dlouho. Z této úvahy vyplývá kritérium, které by měl každý „test“ splňovat — nezbytná je záruka, že odpověď dostaneme v konečném čase. Jestliže existuje takový test, který vždy skončí v konečném čase, budeme mu říkat rozhodovací procedura daného formálního systému.

Máme-li rozhodovací proceduru, máme i velice konkrétní charakterizaci podstaty všech teorémů systému. Na první pohled by se mohlo zdát, že pravidla a axiomy formálního systému neposkytují o nic méně úplnou charakterizaci vět systému než nějaká rozhodovací procedura — problém je právě ve slově „charakterizace“. Zajisté — odvozovací pravidla a axiomy MIU-systému charakterizují řetězce, jež jsou teorémem, dělají to ovšem implicitně, skrytě. Ne-teorémy charakterizují také, ale ještě skrytěji. Taková skrytá charakterizace ale pro mnohé účely nestačí. Pokud někdo prohlašuje, že dokáže charakterizovat všechny teorémy, ale trvá mu nekonečně dlouho zjistit, že nějaký konkrétní řetězec teorémem není, budeme patrně v pokušení říci, že takové charakterizaci něco chybí — není dostatečně konkrétní. Proto zjištění, že existuje rozhodovací procedura, je velice důležitý krok. Takový objev ve skutečnosti znamená, že můžete testem řetězce zjistit, zda jde o teorém, a třebaže je test složitý, zaručeně skončí. Takový test je v podstatě stejně snadný, stejně mechanický, stejně konečný a dává stejnou jistotu jako zjištění, zda je první písmeno M. Rozhodovací procedura je „lakmusovým papírkem“ vlastnosti být teorémem.

Mimochodem, jedním požadavkem na formální systémy je, že soustava axiomů musí být vybavena rozhodovací procedurou — musí existovat lakmusový papírek na to, zda něco je či není axiom. To přinejmenším zaručuje, že můžeme bez problému začít pracovat. V tom spočívá podstatný rozdíl mezi soustavou axiomů a soustavou teorémů: pro axiomy vždy musí existovat rozhodovací procedura teorémy ji mohou postrádat.

Právě na tento problém jsme narazili při prvním setkání s MIU-systémem. Byl zde jediný axiom, rozhodovací pravidla byla velmi jednoduchá, teorémy byly tedy implicitně charakterizovány — a přesto bylo dost nejasné, k jakým koncům taková charakterizace povede. Konkrétně řečeno: nebylo vůbec jasné, zda MU je či není teorém.

Obr.12 Nebeský zámek, M.C. Escher (dřevořez, 1928).

2. Dvojhlasá invence

Achilles předběhl pana Želvu a pohodlně se usadil na jeho zádech,

„Takže vy jste se nakonec přece jen dostal na konec závodní dráhy?“ pravil Želva. „A to navzdory tomu, že je k tomu zapotřebí provést nekonečně mnoho úkonů? Měl jsem pocit, že nějaký mudrlant nebo někdo takový dokázal, že se to nedá provést?“

„DÁ se to,“ řekl Achilles, „DALO se to! Solvitur ambulando. Rozumíte, jde o to, že ty vzdálenosti se neustále ZMENŠUJÍ, takže.. “ M

„Dobře, ale co kdyby se neustále ZVĚTŠOVALY?“ přerušil jej Želva, „co potom?“

„Pak bych tady asi nestál“ skromně odtušil Achilles, „zato vy byste touhle dobou už měl za sebou hezkých pár koleček kolem světa!“

„Vy mě snad rozpláčete — pardon, chci říci ROZPLÁCNETE,“ pravil Želva, „vy tedy JSTE ve svém oboru pěkně těžká váha, to se musí nechat! Doslova vážený občan! No dobrá, a nechtěl byste se seznámit se závodní drahou, o níž se většina lidí domnívá, že se snadno dostanou na její konec pomocí dvou tří skoků, zatímco VE SKUTEČNOSTI sestává z nekonečně mnoha neustále narůstajících vzdáleností?!“

„No jasně!“ zvolal řecký válečník, zatímco vytahoval z helmy (jen velice málo řeckých válečníků oné éry vlastnilo KAPSY) kolosální zápisník a tužku. „Přehánějte! A mluvte hezky POMALU, prosím! TĚSNOPIS nebyl dosud vynalezen!“

„To úžasné První Tvrzení Eukleidovo!“ mumlal si Želva snivě pod vousy, „doufám že také patřičně obdivujete Eukleidovy poučky!“

„Vášnivě! Aspoň tedy do té míry, do jaké lze obdivovat pojednání, které bude Publikováno až za několik století!“

„Dobrá, soustřeďme se na kousek argumentace z tohoto Prvního Tvrzení — postačí nám dva logické krůčky a závěr z nich plynoucí. Laskavě ši je zaneste do toho vašeho zápisníčku. A abychom si je nepletli, označme si je písmeny A, B a Z...

(A) Objekty, které se rovnají jinému objektu, rovnají se také samy sobě.

(B) Dvě strany tohoto trojúhelníka představují objekty, které se rovnají stejné třetí straně.

(Z) Dvě strany tohoto trojúhelníka se sobě rovnají.

Souhlasíte, že — jak by Eukleidovi čtenáři jistě připustili — Z logicky plyne z A a B, takže kdokoli, kdo přijme A a B za pravdivé, Musí přijmout i Z?“ „Nepochybně! I nejhloupější žáček střední školy — hned jak bude nějaká střední škola vynalezena — na což si tedy ještě takových dva tisíce let musíme počkat — by vám dal za pravdu, že TO platí“

„A kdyby snad nějaký čtenář neuvěřil výrokům A a B, stále by ještě mohl připustit, že takový logický VÝVOD je PLATNÝ, nemyslíte?“

„Takoví čtenáři se jistě najdou. Ti řeknou třeba: ,Uznáváme za pravdivé hypotetické tvrzení, že KDYBY A a B byly pravdivé, pak by platilo i Z, ale NEUZNÁVÁME za pravdivé samotné výroky A a B.“ Takoví čtenáři by udělali nejlépe, kdyby nechali Eukleida Eukleidem a dali se na fotbal“

„Ale nemohl by se najít i DALŠÍ čtenář, který by řekl: Beru A a B, ale neberu hypotetickou implikaci...?“

„To by jistě mohl. Ten by ROVNĚŽ dobře udělal, kdyby se dal na fotbal...“

„Avšak ani jednoho z těchto čtenářů“ pokračoval Želva, „ZATÍM žádná logika nikterak nenutí uznat, že platí také Z.“

„Tak jest,“ přitakal Achilles.

„Dobře. A já bych si teď přál, abyste MĚ považoval za čtenáře tohoto DRUHÉHO typu, a donutil mě, logicky, abych musel uznat, že platí Z.“

„Želva, která hraje fotbal, to by byla...,“ začal Achilles.

„...anomálie, samozřejmě,“ přerušil jej Želva zprudka. „Ale neodvádějte řeč od podstaty věci. Nejprve vyřídíme Z, a hned potom fotbal!“