Student World

Gödelova věta by mohla být nejenom výrazem jisté bezmoci, ale je snad použitelná i pro "pozitivní" matematické důkazy? Můžeme zjistit, zda daný program řešící určitou úlohu je ten nejkratší možný? Můžeme zjistit, zda daná posloupnost je dále nekomprimovatelná? A také ještě k diskusi kolem matematického formalismu…

Diskuse u článku "Pravdivost, dokazatelnost, konzistence: Nad důsledky Gödelových vět"
http://www.scienceworld.cz/sw.nsf/ID/DB7DBF9EC58194D3C1256F0E004B34BC?OpenDocument&cast=1
stejně jako několik diskusí dalších (především ve vztahu k některým tvrzením v Barrowově knize Pí na nebesích) si snad zaslouží ještě několik komentářů. Zdůrazňuji předem, že půjde o glosy vyznačující se z mé strany značnou míru nejistoty, současně budou ale asi sotva všeobecně srozumitelné….

Jako první zajímavost: Barrow uvádí svérázné (hypotetické) využití Goedolových vět ve smyslu pozitivního matematického důkazu – to je hodně nezvyklé, protože je to vlastně opačné, než prvoplánová interpretace Goedela jako překážky dospět k nějakému rozhodnutí. Představte si tedy, že by se Fermatova věta (přidržme se příkladu z knihy Pí na nebesích, přestože tento problém konkrétně už byl mezitím vyřešen) prokázala být v systému nerozhodnutelná. To by podle Barrowa znamenalo, že je nutně pravdivá. Můžeme totiž hypoteticky nechat generovat čísla a testovat příslušnou (ne)rovnost. Pokud by existovala rovnost, nalezli bychom ji, byť v neomezeném čase. Pokud by to podle Goedela nebylo z principu možné, znamenalo by to, že věta musí nutně platit (ovšem při tomto myšlenkovém postupu de facto musíme vyskočit ze systému).
Jaký máte názor na takovýto způsob důkazů? Ve skutečnosti je otázka zřejmě spíše teoretická, protože u "faktických" problémů typu Fermatovy věty přichází asi těžko do úvahy prokázat jejich nerozhodnutelnost.
Dokonce ale i kdybychom uznali tento druh důkazu a dokázali nerozhodnutelnost problému, nemusí to vždy stačit. Např. u problematické věty o nekonečném počtu dvojic prvočísel lišících se navzájem o 2 nám toto nijak nepomůže. Proséváním prostoru čísel na nekonečně rychlém počítači totiž nemůže dát v tomto případě žádný závěr (je srozumitelný rozdíl mezi tímto problémem a Fermatovou větou?).

Nyní k druhému okruhu problémů, které se týkají komprese a optimálních algoritmů. Barrow uvádí, že z Godela podle něj vyplývá ekvivalentní zjištění, že totiž:
– o žádné posloupnosti nikdy nevíme, zda je maximálně komprimovaná
– o žádném programu řešícím danou úlohu nemůžeme vědět, zda je ten nejkratší možný.

Vitas k tomu v komentáři napsal:
"Myslím, že autor prohodil kvantifikátory: neexistuje obecný způsob jak pro libovolnou úlohu určit zda program ji řešící je nejkratší. Ale pro některé konkrétní úlohy toto rozhodnout zajisté dokážeme.
Kupříkladu úlohu zvětšení čísla o 1 řeší naprosto jistě nejkratší program: inc(číslo).
Samozřejmě záleží na zvolené definici délky, definici ‚programu‘ a pod. Nicméně ať si laskavý čtenář zvolí libovolnou definici určitě si najde úlohu a i dokazatelně nejkratší program který ji řeší. V onom zmiňovaném důsledku jde spíše o to, že ne všechny úlohy touto vlastností oplývají."

Domnívám se, že Vitas má pravdu. Bez ohledu na to, zda délkou algoritmu míníme nějaký zápis ve strojovém kódu nebo v definovaném programovacím jazyce, pak (snad :-)):
– pro danou úlohu máme k dispozici hypotetický program, který ji řeší
– potom můžeme vygenerovat veškeré kratší programy a zjistit, zda úlohu řeší a najít ten nejkratší
– náš úkol se tedy redukuje na zjištění, zda daný program úlohu skutečně řeší
– za "úlohu" nepokládáme v tomto případě slovní popis, ale už nějak formalizované zadání. Pak by vlastně úloha a algoritmus pro její řešení měly být na sebe nějak převoditelné sadou operací – alespoň v rozumných případech typu zvětšení čísla o 1.
– obávám se, že do problému bychom se zřejmě dostali podobně jako u problému zastavení – prostřednictvím nějaké sebereference. Např. "zjistěte, zda daný program dokáže v nejkratším čase správně určit, zda zadaný program řeší danou úlohu" (tj. test pro úplně obecné vstupy "program" a "úloha").
Jaký máte na toto názor?

K maximální kompresi. Opět se na základě diskusí domnívám, že můžeme zjistit, zda řada X je dále nekomprimovatelná. Představme si to tak, že vlastně hledáme nejkratší program/Turingův stroj/předpis, který vygeneruje určitou řadu. Opět "výčtem" lze asi zjistit, že nic kratšího řadu XY nevygeneruje. No a pokud je takovýto nejkratší předpis stejně dlouhý jako samotná řada, pak je prostě nekomprimovatelná. Přiznám se tedy, že v tomto bodě Barrowově argumentaci nerozumím.

Na závěr tohoto článku ještě jeden komentář obhajující matematický formalismus, který do diskuse napsal Mefisto:
"…Nám stačí ke štěstí, když ty naše shluky písmenek jsou krásné, občas dobře ladí s jevy, jež pozorujeme ve světě kolem nás, umožní nám nahlédnout do některých přírodních zákonitostí…"
Jenomže, jak vidíte, vlastně ty své shluky písmenek také podrobujete určitým požadavkům. Nepožadujete sice, aby nějak korespondovaly s nějakou platónskou pravdou, nicméně některé shluky písmenek a operace s nimi pokládáte za "hezčí". Tj. ani pro vás to nejsou jen formální shluky písmenek (pak by žádný z nich nic neznamenal a byly by všechny zcela ekvivalentní), ale odkazují k něčemu dalšímu – pouze tam, kde by se Godel odvolával na nějakou ideu "pravdy", máte vy zřetele řekněme estetické. To mi přijde vlastně stále v souladu s platónským chápáním světa :-).

autor Pavel Houser