Počítač je mechanický stroj, podobne ako auto či lietadlo, avšak jeho funkcia nie je tak jednoznačne daná. Oproti iným strojom sa počítače líšia tým, že sa dajú programovať a ich funkcia sa mení podľa toho, aký program počítač “vykonáva”. Z tohto pohľadu tak vznikajú zaujímavé otázky, napríklad - “čo sa nikdy nebude dať naprogramovať?”

• Synax a sémantika
• Naša realita - formálny systém
• Čo teda počítač vedieť nebude
• Začiatky - Matematická kríza a Hilbertov program
• “De-paradoxizácia”
• Principia Mathematica
• Teorém nekompletnosti
• Entscheidungsproblem
• Záver

Naprogramovať nejaký algoritmus na počítači znamená prepísať riešenie, ktoré máme v hlave vymyslené do formálneho zápisu daného programovacieho jazyka. Inak povedané, programovací jazyk reprezentuje formálny systém, ktorý má definované “symboly” (kľúčové slová, literály, riadiace prvky, atď.) a syntaktické pravidlá, ktoré definujú, v akom poradí alebo v akých miestach je dovolené použiť aké-ktoré symboly.

Naprogramovať algoritmus teda znamená prepísať intuitívne chápanie tohto riešenia, ktoré máme v hlave, do formálneho - syntakticky obmedzeného - zápisu.

Keď sa nad tým zamyslíme, počítač intuitívne nechápe sémantiku (význam) toho, čo robí. Každý program je pomocou kompilátora preložený do elementárnych krokov, ktoré počítač dokáže vykonať. Tieto kroky sa nazývajú inštrukcie, a sú veľmi univerzálne. Sami o sebe teda ani neumožňujú pochopiť sémantiku celého algoritmu, iba ak sa pozrieme na inštrukcie ako celok “zvonku”. To však počítač nedokáže - pri vykonávaní programu počítač vidí (zjednodušene) len jednu inštrukciu v čase. Postupne prechádza od prvej až k poslednej, a každú z nich mechanicky (bez ďalšieho “rozmyslu”) vykonáva.

Počítač je teda systém, ktorý je “uzavretý” - nevie mať “nadhľad”. Nerozhoduje sa podľa metafyzického významu, intuitívneho chápania, ktoré by prichádzalo apriórne. Je obmedzený len na to, čo je definované v počítači samotnom.

Synax a sémantika

Vo všeobecnosti vo svete existujú dve druhy právd - syntaktická a sémantická pravda. Syntax jazyka obmedzuje možnosti toho, čo v jazyku vieme vôbec vyjadriť. Podľa toho, ako “voľná” je syntax, tak “zložité” výroky vieme povedať v tomto jazyku. Ak porušíme syntaktické pravidlá, výroky prestávajú dávať zmysel. Syntaktická pravda je teda vyjadrenie, či výrok dáva alebo nedáva zmysel. Napríklad výrok “bude” sám o sebe zmysel nedáva, pretože syntakticky chýbajú podmet a prísudok.

Sémantická pravda hodnotí pravdivosť výroku už využitím jeho významu. Avšak na to, aby sa dal pochopiť význam výroku, musí byť tento výrok už syntakticky validný (syntakticky pravdivý). Napríklad, výrok “dnes je pekne” už umožňuje zamýšľať sa o jeho pravdivosti, pretože syntakticky dáva zmysel. Teda každý sémanticky pravdivý výrok musí byť pravdivý aj syntakticky, ale naopak to platiť nemusí.

Ak by sme chceli napísať všetko sémanticky pravdivé, čo vo svete platí, môžme sa o to pokúsiť systematickým spôsobom. Ako by však mal vyzerať takýto systematický spôsob? Na to, aby sme nejaký našli, alebo prehlásili, že to nejde, sa potrebujeme zamyslieť nad sémantickou “pravdou” samotnou - čo to je “pravda”?

Intuitívne chápeme pravdu ako výrok, ktorý “platí”. Ale výrok môže platiť len relatívne - tj. len vo svete, ktorý poznáme. Existujú ale výroky, ktoré platia aj absolútne (objektívne)? Na túto otázku existujú rôzne odpovede a názory, ktoré vyústili do filozofických smerov, ako napríklad pozitivizmus, formalizmus a realizmus.

Naša realita - formálny systém

Keď sme rozoberali možnosť existencie relatívnej pravdy, logicky by mohli existovať niekoľko rôznych “svetov”, a v každom z nich budeme vedieť odvodiť jemu vlastné výroky a zamýšľať sa nad ich pravdivosťou v danom svete. Takýto “svet” sa medzi formalistami začal nazývať formálny systém.

Formálny systém definuje “svet”, v ktorom môžme tvoriť výroky a odvodzovať jednoduchšie výroky do zložitejších. Na tvorbu a odvodzovanie výrokov systém definuje presné pravidlá. Vo všeobecnosti má definované:

• symboly,
• povolené spôsoby dedukcie (pravidlá odvodzovania),
• axiómy (zapísané len pomocou symbolov a pravidiel odvodzovania).

Axiómy tvoria základné pravdy, ktoré už nie je možné rozložiť na ešte “základnejšie” pravdy. Je to “základ sveta”, jeho “definícia”. Tým, že sa jednotlivé formálne systémy líšia - majú rôzne axiómy, symboly a pravidlá odvodzovania, tak každý systém svojim spôsobom definuje svoju relatívnu sémantickú pravdu.

Sémantickú pravdu vo formálnom systéme vieme mechanicky odvodiť - teda dokázať, či daný výrok je pravdivý, alebo nepravdivý. Majme teda výrok X, ktorý je v danom formálnom systéme syntakticky validný. Jeho pravdivosť vieme dokázať tak, že sa pokúsime “znovuobjaviť” tento výrok:

1. aplikáciou povolenéných pravidiel odvodenia na axiómy, čím vzniknú prvé zložené výroky
2. Porovnáme nový výrok s výrokom X. Ak sú výroky zhodné, prehlásime X za pravdivý.
3. Pokračujeme aplikáciou pravidiel odvodenia na zložené výroky, čím vytvárame ďalšie výroky
4. Opakujeme body 2 až 3 dovtedy, kým sme neodvodili všetky možné výroky, alebo nenašli zhodu s výrokom X. Ak po vygenerovaní všetkých výrokov sme stále nedospeli k výroku X, tak je výrok X nepravdivý.

Pri troche šťastia sa nám podarí odvodiť výrok, ktorého pravdivosť chceme zistiť. Ak sa to podarí, tak výrok môžme prehlásiť za “sémanticky pravdivý” v danom formálnom systéme. Samozrejme, je dôležité odvodzovať výroky systematicky, aby v tom nebol chaos.

Formálny systém je zaujímavá abstrakcia aj preto, lebo podľa toho, akú “voľnosť” dávajú pravidlá odvodzovania, takú “vyjadrovaciu silu” daný formálny systém má. Ak je formálny systém dostatočne silný (napríklad umožňuje odvodiť aritmetiku - pravidlá počítania), paradoxne prestane ponúkať možnosť odvodiť všetky sémantické pravdy. Inými slovami, existujú výroky syntakticky validné v tomto formálnom systéme, ktoré z formálneho systému nebudeme vedieť odvodiť - teda ich nebudeme vedieť dokázať.

Ak zhrniem najdôležitejšie doterajšie poznatky:

• Syntaktická správnosť (pravda): je vždy mechanicky overiteľná
• Sémantická správnosť (pravda): nie je vždy mechanicky overiteľná v rámci formálneho systému, ale mimo neho (a intuitívne) áno

Čo teda počítač vedieť nebude

Intuitívne - počítačom budeme vedieť naprogramovať len problémy, ktoré nebudú vyžadovať intuitívne chápanie. Teda všetko to, čo sa dá vypočítať “mechanicky”, len slepým nasledovaním pravidiel “formálneho systému”.

Toto tvrdenie je dôležité preto, lebo sa ukazuje, že to, čoho je sémantika schopná pochopiť intuitívne, tvorí “väčšiu množinu” než to, čoho je možné dosiahnuť mechanickým odvodzovaním (vykonávaním). Inými slovami, vieme vytvoriť výroky, ktoré sa mechanickým odvodzovaním nedajú odvodiť, ale predsa sú syntakticky validné a sémanticky pravdivé.

Jednými z prvých prelomovýmých aktérov v dokazovaní týchto tvrdení boli Kurt Gödel a Alan Turing:

1. Gödel ako logik a metamatematik ukázal, že v určitých formálnych systémoch existujú výroky, ktoré sú pravdivé, ale nedajú sa dokázať (vytvoril taký výrok a poskytol dôkaz jeho “nedokázateľnosti”) (Teorém nekompletnosti)
2. Turing zas dokázal, že sa nedá nájsť ani žiadny mechanický proces (algoritmus), ktorý by vo všeobecnosti vedel buď dokázať daný výrok, alebo skončiť s tým, že je výrok “nedokázateľný” (Entscheidungsproblem)

Začiatky - Matematická kríza a Hilbertov program

Pred rokom 1900 vedci postupne začali dôverovať sile “metódy” a racionalite. Devätnáste storočie prinieslo mnoho prelomových teórií a objavov, ale mnohé ostali stále neobjasnené. Detaily a zložitosť, ktoré nové objavy začali prinášať, sa niektorým vedcom začali javiť ako predzvesť akéhosi limitu možností ľudského chápania (namiesto optimizmu k ďalším objavom).

Jedným z nich bol nemecký fyziológ Emil du Bois-Reymond, ktorý napísal knihu Über die Grenzen des Naturerkennens, v ktorej popularizoval sedem “svetových hádaniek”. Tri z nich (prvú, druhú a piatu) označil za vedecky aj filozoficky neriešiteľné:

1. ultimátna podstata hmoty a sily
2. pôvod pohybu
3. pôvod jednoduchých ľudských zmyslov

Argumentom však bol iba obyčajný agnosticizmus. Emil tvrdil, že ide o “transcendentné otázky” (mimo možností chápania človeka). Na konci každej “otázkovej” kapitoly oznámkoval kurzívou napísané latinské slovo Ignorabimus (nebudeme vedieť). Toto slovo nakoniec Emil použil aj vo svojej slávnej reči pred Pruskou akadémiou vied vo výroku ignoramus et ignorabimus:

Nevieme a nebudeme vedieť.

Tomuto prístupu sa postavil na odpor (svojej doby asi najslávnejší) nemecký matematik David Hilbert, ktorý bol zhodou okolností jedným z prvých propagátorov používania formálnych systémov. Hilbert bol veľmi citlivý na tento Ignorabimus aj preto, lebo matematika začiatkom 20. storočia prežívala vážnu krízu, z ktorej bol Hilbert frustrovaný. Hilbert však veril, že je možné nájsť riešenie a preto nechcel slepo prijať ignoranciu.

Kríza spočívala hlavne v tom, že samotné základy vtedajšej matematiky - naivná teória množín, umožňovala tvorbu paradoxov - teda výrokov, ktoré platia a neplatia zároveň. Nebezpečie spočíva v tom, že ak tvrdenie P platí aj neplatí, pravidlo modus ponens (z P vyplýva Q) nám umožní odvodiť prakticky čokoľvek, aj nepravdivé výroky a celá matematika sa tak zrúti ako domček z karát.

Táto kríza doviedla Hilberta ku spísaniu 23 dovtedy známych matematických problémov, ktoré odprezentoval na Parížskom kongrese v roku 1900. Tam vyzval matematikov, ako svoju armádu, k ich riešeniu. V roku 1932, keď odchádzal do dôchodku, zhrnul svoju záverečnú reč aj v rádiu, kde okrem iného povedal:

Nesmieme veriť tým, ktorí dnes s oporou filozofie a nadradeným tónom predpovedajú úpadok kultúry a akceptujú Ignorabimus. Pre nás nie je žiadny Ignorabimus, a podľa mňa ani v žiadnej prírodnej vede. Namiesto hlúpeho Ignorabima nech náš slogan znie: Musíme vedieť. Budeme vedieť.

Niektoré príklady Hilbertovho programu:

• Dokázať hypotézu kontinua: že neexistuje množina, ktorej kardinalita by bola presne medzi množinou prirodzených a reálnych čísel
• Dokázať konzistenciu axiómov aritmetiky len v rámci formálneho systému aritmetiky
• Nájsť algoritmus, ktorý pre každú Diofantickú rovnicu odpovie, či táto rovnica má alebo nemá riešenie, keď sa za neznáme dosadia len celé čísla

“De-paradoxizácia”

Už Aristoteles (4. stor. pred n.l.) si všimol, že vo vetách sú dôležité len určité slová, a zvyšok nemá vplyv na “logickosť” výroku, ktorý sa tak dá nahradiť premennými. Avšak prvé pravidlá odvodzovania výrokovej logiky, o ktorej v podstate hovoríme, objavili nezávisle na sebe v úplne rôznych historických obdobiach Chrisippus (3. storočie pred n.l.), Peter Abelard (12. storočie), Gottfried Leibniz (17-18. storočie), s ďalšími rozšíreniami od Georgea Boola a Augusta De Morgana.

Až Gottlob Frege prišiel s jeho logikou prvého rádu (predikátovou logikou), ktorú definoval pomocou naivnej teórie množín (Cantor). Predikátová logika pridáva možnosť použitia všeobecných kvantifikátorov a ukázal, že pomocou nej je možné formálnym spôsobom zapísať axiómy aritmetiky, čo bol veľký krok k ďalšej formalizácii.

Frege očakával tri predpoklady dobrej matematickej teórie:

1. je konzistentná: nemožnosť dokázať protichodné tvrdenia
2. je úplná: každý výrok je buď dokázateľný alebo zamietnuteľný (tj. jeho negácia je dokázateľná)
3. je rozhodnuteľná (existuje “rozhodovacia procedúra”, ktorá dokáže overiť pravdivosť každého výroku)

Avšak Fregeho logika s rozšírením o pravidlá aritmetiky bola nekonzistentná. Prišiel na to aj Bertrand Russel, ktorý vytvoril “paradoxnú” množinu, známu aj pod názvom Russelov paradox:

Zostrojme množinu, ktorá obsahuje všetky množiny neobsahujúce samých seba.

Patrí práve definovaná množina do samej seba? Ak nie, tak by tam patriť mala - podľa definície. Ak ju tam však pridáme, tak by obsahovala samu seba a teda - podľa definície - by sme ju mali odobrať. Takáto množina sa nedá zostrojiť, ide o logický paradox.

A práve kvôli paradoxom sa veľa diskutovalo o vzťahu matematiky a reálneho sveta:

• Je matematika len výplodom ľudskej predstavivosti? (čo by mohlo znamenať, že paradoxy sú tiež len výplody ľudskej predstavivosti a nemá zmysel sa nimi zaoberať),
• Alebo popisuje matematika reálny svet? (čo by znamenalo, že paradoxy sú dôležitými ukazateľmi toho, že niečo nechápeme správne)

Na základe týchto a podobných otázok vznikali rôzne názorové smery, hlavne formalizmus, intuicionizmus a logicizmus:

K vyššie uvedenému “stromu” treba povedať, že sa niektorí matematici ťažko radia do jedného vyhradeného smeru, pretože svojou prácou prispeli k viacerým smerom. Taktiež, matematický realizmus ako taký nevznikol ako priama odpoveď na otázku krízy, existoval už dávno predtým ako presvedčenie, že matematika sa nedá oddeliť od intuitívneho (reálneho) sveta.

Principia Mathematica

Jedným z cieľov formalistov, hlavne Hilberta, bolo “sformalizovať” celú dovtedy známu matematiku, pretože formalisti zastávali názor, že dôvod možnosti vzniku paradoxov je dovolenie definovania axiómov intuitívne. Formalisti verili, že pravdy v matematike sú konzistentné a úplné, ak ich vieme odvodiť len z formálneho systému, ktorý obsahuje, ako som už uviedol - premenné, axiómy (zapísané v jazyku tohto systému a nie intuitívne) a pravidlá na manipuláciu s axiómami.

Tento cieľ vyžadoval vytvorenie jednotného formálneho jazyka (notácie a deduktívneho systému), v ktorom by bolo možné nielen matematiku zapísať, ale aj odvodiť všetky dôkazy tvrdení. Jazyk by mal spĺňať vlastnosti dobrej matematickej teórie, ako ich definoval Frege (konzistencia, úplnosť a rozhodnuteľnosť).

Matematici Betrand Russel a Alfred Whitehead sa chopili tohto problému, pretože verili, že Fregeho logika prvého rádu by mohla byť použitá ako základ, s “drobnými úpravami”. Tieto “drobné úpravy” spočívali v nahradení naivnej Cantorovej teórie množín z Fregeho logiky niečim iným - dobrým axiomatickým systémom; ako vhodné sa javili Peanove axiómy aritmetiky.

Russel s Whiteheadom si mysleli, že majú všetko potrebné už pripravené, stačí to len “dať do kopy”.

Začali písať trojzväzkovú knihu s názvom Principia Mathematica (roky 1910, 1912, 1913). Napísať prvý zväzok trvalo však príliš dlho, Russelovi sa stále nedarilo odvodiť všetky dôkazy len z týchto axiómov a logickej dedukcie. Nakoniec ho Whitehead prinútil knihu vydať tak ako je. Zaujímavosťou tejto knihy je napríklad dôkaz (so všetkým potrebným na zhruba 300 strán), že \(1 + 1 = 2\):

O chýbajúcom dôkaze konzistencie axiómov aritmetiky sa už vedelo, dôkaz požaduje Hilbert v jeho druhom probléme, ale každý to považoval len za “formalitu”, ktorú treba spraviť.

Teorém nekompletnosti

Kurt Gödel prišiel v roku 1929 s tzv. teorémom úplnosti predikátovej logiky, v ktorom dokázal, že Fregeho klasická predikátová logika (bez rozšírenia o aritmetiku) je úplná. To znamená, že mechanickou procedúrou (algoritmom) vieme odvodiť všetky pravdivé výroky tejto logiky.

A tak Gödel pokračoval v práci na druhom Hilbertovom probléme - konzistencii aritmetiky. Počas tejto práce objavil jeho najslávnejší teorém: teorém nekompletnosti (publikoval ho roku 1931). Boli to v podstate dva teorémy, no z prvého vyplýva druhý:

Žiadny konzistentný systém axiómov, dostatočne silný na odvodenie aritmetiky a ktorého výroky vieme systematicky odvodiť, nie je schopný dokázať všetky pravdivé výroky

A druhý teorém:

Takýto systém nemôže dokázať vlastnú konzistenciu.

Gödel odvodil tento teorém zo snahy formálne zapísať variantu paradoxu klamára (jeden z najstarších paradoxov vôbec):

• Jeden Kréťan povedal, že všetci Kréťania sú klamári. … Klame či neklame tento Kréťan?
• Iný variant: Holič holí len mužov, ktorí neholia samých seba. … Má sa teda holič sám oholiť, či nie?
• Gödel použil tento variant: Tento výrok je nedokázateľný v rámci tohto formálneho systému

Tento výrok sa mu podarilo zapísať len v symboloch formálneho systému. Vytvoril teda autoreferenčný výrok, ktorý je syntakticky validný. V druhom kroku dokázal, že systematickým spôsobom nie je možné odvodiť z axiómov formálneho systému tento výrok, ale ani jeho negáciu. Z toho vyplýva, že ide o pravdivý výrok - ale vieme to len podľa našej intuície, pretože hovorí pravdu - nedokázali sme odvodiť ani výrok, ani jeho negáciu, teda nie je ho možné dokázať v rámci tohto formálneho systému.

Konzistenciu formálneho systému, ktorý má silu na odvodenie aritmetiky sa nakoniec podarilo dokázať, ale pomocou iného formálneho systému. Dokázal ju [Gentzen][63] v roku 1936.

Dôsledky tohto teorému sú veľmi závažné, pretože z neho vyplýva, že v čisto formálnej matematike môžu existovať výroky, ktoré budú pravdivé, ale nebudú sa dať dokázať (ako si napr. myslel aj strýko Petros o Goldbachovej domnienke :). Gödel tento výsledok prezentoval na matematickej konferencii v Kráľovci, na ktorej bol aj John von Neumann! A bol to jediný z prítomných, ktorý si tento výsledok dal do súvislostí a prehlásil: “it’s all over”.

Von Neumann bol jedným z hlavných propagátorov Gödela a jeho výsledkov a vďaka nemu sa Gödel mohol dostať na IAS, kde pôsobil aj Albert Einstein a iní významní matematici a fyzici.

Entscheidungsproblem

David Hilbert sa nikdy nevyjadril ku Gödelovemu výsledku. Podľa niektorých indícií prežíval Hilbert hnev a frustráciu. Avšak - podľa Fregeho “dobrej matematickej teórie” ešte stále chýbal dôkaz rozhodnuteľnosti, známy pod názvom “Entscheidungsproblem”. Tento problém Hilbert formuloval ešte pred objavom teorému nekompletnosti, roku 1928, takto:

Nájsť všeobecný algoritmus, ktorý by na vstupe dostal formálny výrok a výstupom by bola odpoveď typu “Áno”/”Nie” (rozhodnutie), či je výrok univerzálne (vo všeobecnosti) pravdivý.

Programátorom môže Entscheidungsproblem pripomínať problém známy ako “SAT” (Boolean satisfiability problem), ktorý sa dá formulovať nasledovne:

Je možné nájsť také hodnoty premenných daného formálneho výroku, aby výrok platil?

Rozdiel teda spočíva v tomto:

• V Hilbertovom probléme hľadáme všeobecnú odpoveď pre všetky možné hodnoty premenných. Inak povedané, snažíme sa redukovať výrok na hodnotu “True” alebo “False” bez dosadzovania konkrétnych hodnôt za premenné,

• V SAT probléme hľadáme také hodnoty premenných, aby výrok v tejto jednej inštancii platil, ale nemusí platiť pri iných hodnotách premenných. Hľadáme teda odpoveď “v jednej inštancii”.

Záver

V tejto prvej časti môjho príspevku som sa snažil priblížiť pozadie filozofického a matematického sveta na začiatku 20. storočia, ktoré viedlo k veľkému matematicko-filozofickému objavu. Tento objav, teorém nekompletnosti, dáva do súvislosti dedukciu, logiku a filozofiu. Popiera matematický relativizmus, prúd, ktorý je aj dnes ešte dosť populárny pod pojmom - “všetko je relatívne”.

Matematici 20. storočia ako napr. Hilbert a potom hlavne pozitivisti, verili v myšlienku “relativizmu” - matematika je len dielom, výtvorom, človeka, a ako myšlienkový nástroj má málo spoločné s reálnym svetom. Gödel naopak veril, že matematika s reálnym svetom súvisí a nie je ju možné od neho oddeliť. Práve teorém nekompletnosti vyjadruje tento vzťah. Existencia diskrétnych a počitateľných objektov v tomto svete, ak existujú izolovane len v tomto svete, sú podľa Gödela paralelou ku axiomatickému systému aritmetiky. Tým pádom, nadnesene povedané, je možné, že reálny svet skrýva pravdy, ktoré nikdy nebudeme vedieť pochopiť.

V druhej časti článku sa budem zaoberať problémom rozhodnutia, známym pod názvom Entscheidungsproblem. Popíšem hlavne prácu Alana Turinga, ktorý “konečne dobre definoval algoritmus”.