Môj kód Programovanie v príkladoch

Limity počítačov a myslenia (2/2)


Kladné riešenie problému rozhodnutia, Entscheidungsproblem, ostávalo už ako posledná nádej Hilbertovho programu na formalizáciu matematiky. Po Gödelovom teoréme nekompletnosti bolo jasné, že nie všetky pravdivé výroky sa dajú dokázať. Teraz bolo potrebné nájsť odpoveď na otázku, či sa dá nájsť všeobecný postup, algoritmus, ktorý pre ľubovoľný výrok ho buď dokáže, alebo vyvráti či odpovie negatívne v prípade jeho nedokázateľnosti.

Mechanický proces

Entscheidungsproblem vyzýva ku nájdeniu “algoritmu”, teda mechanického procesu, ktorý by systematickým spôsobom vedel prehľadávať celý “priestor” formálneho systému, až by našiel hľadaný výrok. Keby v priebehu cesty tento výrok našiel, prehlásil by “Áno” (výrok je všeobecne pravdivý), inak by prehlásil “Nie” (výrok nie je všeobecne pravdivý), aj keby to znamenalo, že je nedokázateľný.

“Mechanický proces”, alebo “algoritmus” je zoznam krokov, ktoré reprezentujú všetko potrebné rozhodovanie, ktorého slepým nasledovaním dosiahneme požadovaný cieľ. Nepotrebujeme teda ďalej rozmýšľať nad jednotlivými krokmi, každý krok je jasný a presný. Algoritmus nemá nejednoznačnosti.

Slovo “algoritmus” má dávny pôvod. Pochádza z 9. storočia (odvodené z mena perzského matematika al-Khwarizmi), a používalo sa na označenie postupov operácií s arabskými číslicami. Od 18. storočia sa už intuitívne chápe ako určitý mechanický postup na riešenie nejakého problému či úlohy.

Problému rozhodnutia sa venovali hlavne tri postavy, ktorí nezávisle na sebe a veľmi originálnym spôsobom nielenže podali riešnie daného problému, ale prispeli ku vzniku teoretických a praktických základov samotných počítačov a programovacích jazykov:

  • Alan Turing - jemu sa budem venovať prednostne v ďalších častiach blogpostu,
  • Alonzo Church - okrem riešenia Entscheidungsproblemu (s ktorým prišiel ako prvý) vymyslel aj tzv. Lambda kalkul, ktorý tvorí základ všetkých funkcionálnych programovacích jazykov,
  • ale aj samotný Kurt Gödel, ktorý prišiel s teóriou rekurzie, ktorá sa časom pretransformovala na vedný odbor “teória vypočítateľnosti”.

Turingove stroje

Alan Turing pracoval na Entscheidungsprobleme v 30-tych rokoch minulého storočia. Výsledky jeho práce publikoval v jeho slávnom článku “On computable numbers with application to Entscheidungsproblem” z roku 1937.

Na to, aby mohol dokázať/vyvrátiť existenciu všeobecného algoritmu - mechanického procesu - na problém rozhodnutia, potreboval vytvoriť formálny systém, v ktorom by tento algoritmus mohol zapísať. Potreboval vymyslieť symboly, axiómy a pravidlá odvodenia, pomocou ktorých by vedel zapísať “výrok” samotného algoritmu.

Pri snahe sformalizovať “mechanický proces” hľadal inšpiráciu v človeku samotnom. Človek si popri premýšľaní zapisuje medzivýsledky a konečný výsledok. Premýšľanie si Turing predstavoval ako diskrétnu zmenu “stavu mysle”, ktorá viedla k zapísaniu ďalšieho medzivýsledku, alebo výsledku do zošita. Podľa medzivýsledku v zošite a aktuálneho “stavu mysle” človek “premýšľaním” dôjde do ďalšieho “stavu mysle”, ktorý vedie k zapísaniu ďalšieho medzivýsledku, atď. až kým nie je vypočítaný celý príklad.

Turing pritom dobre chápal, že stačí existencia konečného počtu symbolov s priradeným významom (zvlášť pre každý algoritmus), a pre jednoduchosť predpokladal, že matematik používa štvorčekovaný zošit, pričom do jedného štvorčeka zapíše vždy maximálne jeden symbol:

Matika

Tento proces počítania sa mu podarilo formalizovať do abstraktného počítacieho “stroja”, dnes známeho pod názvom Turingov stroj (T.S.):

Turingov stroj

T.S. používa nekonečnú “pásku”, ako náhradu štvorčekovaného zošita. Samotný T.S. je reprezentovaný tzv. čítaco-zapisovacou “hlavou”, ktorá predstavuje samotné premýšľanie ako black-box. Definované je len to, že táto “hlava” dokáže v jednom čase:

  • zapísať/vymazať jeden symbol na/z pásky,
  • posunúť “hlavu” na nasledujúci/predchádzajúci symbol pásky
  • na základe aktuálneho stavu a symbolu na páske (na ktorý hlava ukazuje) zmeniť stav

Takto zadefinovaný abstraktný stroj, ako Turing ukázal v jeho článku, umožňoval zapísať každý algoritmus. Napríklad, výstup nekonečnej sekvencie 0 1 0 1 0 1 ... sa dá zapísať do tabuľky:

Aktuálny Stav Aktuálny symbol   Zápis symbolu Posun hlavy Nový stav
b nič   0 doprava c
c nič     doprava e
e nič   1 doprava f
f nič     doprava b

Rozhodovanie T.S. je založené len na tom, čo stroj už “videl” alebo zapísal, a to je reprezentované aktuálnym stavom. Môže tak rôznym spôsobom reagovať na rôzne “sekvencie” symbolov na páske, ktoré videl. Ak sa chce T.S. rozhodovať nad širším kontextom, musí postupne prejsť viacerými symbolmi pásky.

Vypočítateľné čísla

Turing v článku definuje vypočítateľné čísla ako také, ktoré sú vyčísliteľné. Teda také, ktorých číslice vieme zapísať bez akéhokoľvek “záseku” až donekonečna, a to pomocou stroja (či algoritmu). Ako príklad vypočítateľných čísel uvádza čísla ako , , reálne korene algebraických rovníc, atď. Aj prirodzené číslo sa dá zapisovať “donekonečna” - buď pred ním budeme donekonečna vypisovať číslicu 0, alebo za ním môžme zapísať desatinnú čiarku a za ňou nekonečný počet číslic 0. V oboch z prípadov sa význam nezmení.

T.S., ktoré zodpovedajú vypočítateľným číslam Turing označil ako circle-free (“bezcyklové”). To môže byť trochu mätúce, pretože “circle-free” stroje sú chápané ako také, ktoré nikdy neprestanú vypisovať symboly výsledku na pásku. Nemajú teda “premýšľacie zacyklenie”. Turing chcel týmto vyjadriť, že circle-free stroje sa vždy “posúvajú vpred”, že “počítajú”.

Aj keď vypočítateľné čísla tvoria nekonečnú množinu, Turing tvrdí, že existujú aj čísla, ktoré vieme iba “definovať” (teda zapísať algoritmus), ale nevieme ich vyčísliť, teda vypočítať (algoritmus v tomto prípade nikdy neskončí). T.S., ktoré odpovedajú takýmto číslam, Turing nazval circular (“zacyklené”). Opäť vysvetlenie - “circular” v zmysle “premýšľacieho zacyklenia”, teda že stroj prestane vypisovať výsledok na pásku (prestane sa “posúvať vpred”, “počítať”).

Spočítateľnosť T.S.

Turing v ďalšom kroku ukázal postup toho, ako celú tabuľku, ktorá T.S. definuje, je možné previesť do jediného prirodzeného čísla. Postup prevodu je priamočiary - symboly sa nahradia číslicami, ako aj oddeľovač riadkov tabuľky sa tiež nahradí číslicou. Vznikne tak jediné číslo, ktoré “enkóduje” T.S. Toto číslo Turing označil ako D.N. (Description Number). Každá vypočítateľná sekvencia, alebo vypočítateľné číslo (pomocou circle-free T.S.) má minimálne jednu reprezentáciu D.N.

“Spočítateľnosť” a “vypočítateľnosť” vyjadrujú v podstate tú istú vlastnosť, len sú tieto pojmy používané v iných kontextoch. Tou spoločnou vlastnosťou je možnosť určiť nasledovníka. Spočitateľnosť sa používa v kontexte množín, a vypočítateľnosť v kontexte čísel, funkcií, atď. Napríklad - množina prirodzených čísel je spočítateľná, pretože vieme vždy určiť nasledujúce číslo. Ale množina reálnych čísel nie je spočítateľná, pretože nevieme určiť priameho nasledovníka žiadneho reálneho čísla.

Množina všetkých D.N. je spočitateľná (enumerable), pretože vieme vždy určiť nasledujúce D.N. (lebo je to prirodzené číslo a syntax vieme overiť vždy v konečnom počte krokov). Keďže každé D.N. reprezentuje jeden T.S., tak aj množina všetkých T.S. musí byť spočitateľná. To znamená, že musíme vedieť systematickým spôsobom vypísať všetky T.S. ktoré sa vôbec dajú vytvoriť.

Číslo, ktoré sa dá vypočítať pomocou circle-free D.N. označil ako “uspokojujúce” (“satisfactory”). A Turing dopredu prezrádza, že nie je možné nájsť všeobecný algoritmus, ktorý by zistil, či dané číslo je alebo nie je “uspokojujúce”.

Univerzálny T.S.

V ďalšom Turing definoval stroj, ktorý je schopný vypočítať ľubovoľné “vypočitateľné číslo”. Na vstup dostane D.N. daného výpočtu, a výsledkom bude to isté, čo by vypočítal T.S. reprezentovaný vstupným D.N. Princíp tohto stroja je založený na vytvorení ďalších symbolov a spôsobom enkódovania vstupného T.S. Univerzálny T.S. je teda akýmsi “simulátorom” T.S.

Ako príklad uvádzam Game of Life verziu univerzálneho T.S.:

Spočítateľnosť vypočítateľných čísel

Nasledujúci krok bolo zistenie, či circle-free D.N. tvoria spočitateľnú množinu. Teda či vieme systematickým spôsobom vypísať všetky vypočitateľné čísla.

Systém vypisovania “nasledovníkov” bol už raz použitý, keď Georg Cantor v roku 1891 dokazoval existenciu nespočitateľných nekonečných množín (množiny reálnych čísel). Použil ho tiež Gödel pri dokazovaní svojho teorému nekompletnosti, a bol použitý aj v Principii Mathematice v popise Richardovho paradoxu. Tento systém je známy pod názvom “diagonálny proces” alebo “diagonálny argument”:

Ak sú vypočítateľné sekvencie spočítateľné, nech je -tá vypočítateľná sekvencia a nech $\phi_n(m)$ je -tá číslica sekvencie . Nech je sekvencia, v ktorej -tá číslica je definovaná ako . Keďže sekvencia je vypočítateľná, existuje číslo , že pre všetky . Ak priradíme , dostávame , teda že číslo je párne. To je nemožné. Vypočítateľné sekvencie teda nie sú spočitateľné.

“Háčik” v spočíva v predpoklade, že je vypočítateľná sekvencia. Ak by bola, v konečnom počte krokov by sme ju vedeli vyčísliť. Avšak problém vyčíslenia vypočítateľných sekvencií je ekvivalentný problému zistenia, či nejaké číslo reprezentuje D.N. circle-free T.S. A takýto proces nemáme - s konečným počtom krokov. Dôkaz tohto tvrdenia bude skúsiť zostrojiť stroj, ktorý počíta sekvenciu .

Nikde nie je povedané presne, čo tento stroj - počítajúci sekvenciu - má robiť. Vieme len, že sekvencia má byť vypočítateľná. Keďže podľa Turinga problém vyčíslenia vypočítateľných sekvencií je ekvivalentný problému zistenia, či nejaký stroj je circle-free, predpokladajme, že máme taký stroj. Teda predpokladajme, že vieme vytvoriť T.S., ktorý dostane na vstupe nejaký ľubovoľný T.S. a výstupom bude odpoveď, či je stroj circle-free.

Jediný spôsob, akým má tento stroj dovolené overovať iné T.S. je simulácia, pretože má ísť o mechanický proces, aplikovaním len pravidiel samotného T.S. Začne teda simulovať postupne jeden stroj za druhým, a na výstupe sa začnú objavovať prvé výsledky. Až kým narazí na samého seba. Simulácia samého seba spôsobí, že sa stroj - teraz pod simulátorom - spustí odznova. A tento simulovaný stroj znova narazí na samého seba, čím sa proces znova zopakuje, až donekonečna.

Týmto myšlienkovým experimentom Turing dokázal, že stroj, ktorý počíta sekvenciu , je circular, teda sekvencia je nevypočitateľná a teda diagonálny argument je správny. Ak by sa Turingovi podarilo dokázať spočitateľnosť circle-free D.N., prišiel by tak trochu do sporu s Gödelovym teorémom nekompletnosti - pretože by to znamenalo, že by sme v podstate vedeli dokázať všetky pravdivé výroky len v rámci formálneho systému.

Limity T.S.

Ako ďalší príklad nevypočitateľnej sekvencie vytvoril T.S. (napr. ), ktorý zisťuje, či nejaký T.S. (napr. ), vypíše aspoň raz nejaký symbol (napríklad ). Turing tvrdil, že ak sa taký stroj nájde, bude dokonca možné zistiť, či tento T.S. bude symbol vypisovať donekonečna. Ako? Na to vytvoril ďalší myšlienkový experiment:

Najprv dokážeme, že ak existuje T.S. , potom existuje všeobecný postup na to, či T.S. bude vypisovať donekonečna. Majme T.S. , ktorý bude vypisovať tú istú sekvenciu ako , ale s tým rozdielom, že miesto prvého symbolu vypíše . Ďalej majme T.S. , ktorý nahradí prvé dva symboly (nie nevyhnutne za sebou) symbolom , atď. Teda, ak vypíše:

potom vypíše:

a vypíše:

atď. Teraz majme T.S. , ktorý bude postupne vypisovať , potom , atď. Skombinujeme s a dostaneme T.S. . Práca bude vyzerať tak, že sa najprv použije na vypísanie , a následne ho otestuje:

  • Ak nikdy nevypíše , tak vypíše
  • Potom vypíše , a ho otestuje. Ak nikdy nevypíše , tak vypíše
  • a tak ďalej.

Teraz otestujme samotný stroj pomocou . Ak sa zistí, že nikdy nevypíše , to znamená, že vypisuje donekonečna. Ak T.S. niekedy vypíše, potom donekonečna nevypisuje.

Takže vo všeobecnosti - schopnosťou zistiť, či daný stroj vypisuje nejaký symbol donekonečna sme práve našli spôsob, ako zistiť, či vstupný T.S. je circle-free. A to je podľa predchádzajúcich výsledkov nemožné. Takže stroj nemôže byť vypočítateľný.

Entscheidungsproblem

Entscheidungsproblem - problém rozhodnutia - požadoval algoritmus, ktorý by vedel odpovedať na otázku, či ľubovoľný matematický výrok predikátovej logiky (s rozšírením o axiómy aritmetiky prirodzených čísel) je vo všeobecnosti platný, alebo nie. Turing teda potreboval nájsť kódovanie takýchto výrokov tak, aby mohli byť vstupom do T.S., ktorý overuje ich platnosť.

Postup bol - ako inak - nájsť taký pravdivý výrok, ktorý nepôjde dokázať žiadnym “mechanickým procesom”. V tejto chvíli bol T.S. už dostatočne silne obhájený ako zástupca všetkých “mechanických procesov” - všetko čo je vypočítateľné, je vypočítateľné na T.S. Takže Turingovi stačilo nájsť výrok, ktorý by reprezentoval nevypočitateľný T.S.:

  1. Zostrojme pravdivý výrok , ktorý reprezentuje nejaký T.S. . Napríklad výrok “ nikdy nevypíše ”.
  2. Ak Entscheidungsproblem je riešiteľný, potom existuje mechanický proces na zistenie, či je dokázateľný.
  3. Podľa predch. výsledkov je dokázateľný vtedy a len vtedy, ak niekedy vypíše
  4. Ak vieme zistiť, či vypíše , potom vieme zistiť, či ľubovoľný T.S. niekedy vypíše
  5. Podľa predch. výsledkov takýto stroj sa zostrojiť nedá
  6. Teda nie je dokázateľný výrok (aj keď pravdivý), čo znamená, že Entscheidungsproblem je neriešiteľný.

Sám Gödel veľmi uznával prácu Alana Turinga. Osobne sa nikdy nestretli, aj keď obidvaja istú dobu pôsobili na IAS-e. Turing tam bol na stáži u Alonza Churcha, ktorý nezávisle na Turingovi (a efektívne skôr) zistil, že Enscheidungsproblem nemá riešenie.

Čo je zaujímavé je, že výsledky všetkých troch velikánov - Gödela, Turinga aj Churcha - sa zhodujú, a ich formálne systémy (teória rekurzie, T.S. a lambda kalkul) sú ekvivalentné. To znamená, že schopnosti a sila každého z týchto formalizmov sú rovnaké. Napr. to, čo je vypočítateľné na T.S. je efektívne vypočitateľné lambda kalkulom, a naopak.

Limity ľudskej mysle

Turingove stroje sú veľmi dôležité z niekoľko hľadísk:

  • Zahŕňajú základné myšlienky ako by mohol fungovať počítač a jeho “programovanie” - “dobre definujú
  • Umožňujú teoreticky skúmať algoritmy (nielen “vypočitateľnosť”, ale aj zložitosť a ďalšie veci)
  • prispievajú určitým spôsobom k agnosticizmu

Teorém nekompletnosti, ako aj nemožnosť riešiť Entscheidungsproblem, prezrádzajú niečo viac aj o povahe nášho sveta, nielen o povahe matematického sveta. Podľa Church-Turingovej tézy je to, čo človek je vôbec schopný vypočítať iba to, čo vypočíta Turingov stroj. Táto téza teda obmedzuje samotného človeka - tvrdí, že človek má úplne rovnaké limity ako Turingov stroj. Keďže hovoríme o práci a myslení človeka, nehovoríme o formálnom systéme. Z tohto dôvodu tézu nie je možné dokázať formálne, avšak intuitívne je úplne akceptovaná.

Predstavme si, že problém rozhodnutia, alebo jemu ekvivalentný - problém zastavenia (Halting problem) (“dá sa zostrojiť T.S. ktorý zistí, či nejaký T.S. zastaví?”) - je riešiteľný. Teda predstavme si, že existuje algoritmus (T.S.), ktorý dokáže riešiť Halting problem. Ak by sme mali takýto algoritmus, mohli by sme napríklad vymyslieť kompilátory, ktoré by automaticky vedeli detekovať, že naše programy sa rútia do nekonečných cyklov, prípadne iné užitočné veci. Tiež by sme mohli vyriešiť ťažké matematické problémy, ako napríklad silnú Goldbachovu domnienku (toto mám z tejto lekcie):

Predstavme si tento algoritmus:

def goldbachConjecture(): Boolean = {
  
  def percolate(n: Int) = {
      for (p <- (2 until n) if isPrime(p))
        for (q <- (p + 1 until n) if isPrime(q))
          if (p + q == n) return true

      false
  }

  var n = 4
  while (true) {
      if (!percolate(n)) return false
      n = n + 2
  }
}

Zastaví niekedy tento program (napísaný v jazyku Scala)? Ak zastaví, potom Goldbachova domnienka neplatí a vyriešime tým veľký matematický problém. Avšak ani keby sme počítaču dali všetky prostriedky na svete (CPU, pamäť) a ani ak by premenné mohli nadobúdať nekonečne veľké hodnoty, ani tak “nevieme a nebudeme vedieť” (ignoramus et ignorabimus), či program niekedy zastaví. To je jeden z priamych dôsledkov neriešiteľnosti Entscheidungsproblemu.

Náznaky ďalšieho vývoja

Od Turingovho článku ubehlo už dosť veľa času. Bezprostredné pokračovanie malo formu skôr opráv (hlavne Emil Post). Ďalej sa ukázalo, že Entscheidungsproblem nie je vôbec jediným problémom, ktorý nemá riešenie (ako napr. spomenutý Halting problem, ale napríklad ani Hilbertov desiaty problém ho nemá).

Postupne sa v priebehu ďalšieho rozvoja “teórie vypočítateľnosti” definovali triedy vypočítateľnosti - ako miera “vyjadrovacej sily”, ktorou systém (napríklad programovací jazyk alebo iný abstraktný stroj či formalizmus) disponuje (viď napr. Turing completeness).

Noam Chomsky definoval hierarchiu formálnych jazykov podľa vyjadrovacej sily, ktorú majú a korešpondoval ich s abstraktnými strojmi a ich vyjadrovacou silou.

Tak vzniklo mnoho ďalších abstraktných strojov a automatov, ktoré ešte lepšie približujú reálne počítače a tým umožňujú ich pohodlnejšie teoreticky skúmať, napr. s vyjadrovacou silou T.S.:

Alebo s menšou vyjadrovacou silou:

Skúmanie zložitosti samotných algoritmov vyústilo do definície tried zložitosti (P, NP, NP-complete, …).

Tiež sa našla súvislosť medzi dokazovaním matematických viet a počítačovými programami (Curry-Howardov izomorfizmus), ktorý hovorí že matematický dôkaz a program na počítači sú si ekvivalentné (je možné previesť jeden do druhého).

Záver

Teória vypočítateľnosti je stále aktívny vedný odbor, ale podľa toho, čo som počul, je len málo ľudí na svete, ktorí sa mu dnes venujú. Ja sám nie som matematik, ani logik. Téma ma zaujala od prvej chvíle - prišla mi veľmi dôležitá, ale nešiel som cestou za príspevkami do tohto vedného odboru. Po rokoch som sa k téme vrátil, pretože som zistil, že nakoniec ide o filozofický problém, ktorý sa dá dobre pochopiť aj bez zamerania na matematiku.

Téma je zároveň veľmi dôležitá - celé je to o tom pochopiť, kde je hranica medzi “objavom” a “výtvorom”. Aj keď je vedľajším produktom hnacích síl “objavu” a “výtvoru” akési obmedzenie, stále je to obmedzenie abstraktné, a dáva pocit akejsi neuchopiteľnosti - a nakoniec - život ide aj tak ďalej.

Popri snahe pochopiť tieto obmedzenia vznikli neuveriteľné veci, ktoré boli smerodatné pre súčasný vývoj počítačov, algoritmov, a programovacích jazykov. Našťastie existuje obrovská množina problémov, ktoré počítače riešiť dokážu, aj keď sami majú len nepatrný “výkon” v porovnaní s Turingovými strojmi. Nekonečná páska T.S. a jeho neobmedzená teoretická rýchlosť samotného vykonávania ho robí tým najvýkonnejším strojom na svete, s absolútnou platnosťou. Napriek tomu ostávajú počítače tie najsofistikovanejšie stroje, aké kedy človek doteraz vyrobil.


Podobné články

Nasleduje: Entropia v BigData

Komentáre