zašto matematika ne može zahvatiti istinu?

Riječ je o daljnjim filozofskim razmatranjima teorema nepotpunosti, odnosno njegove osnovne filozofske posljedice da je matematička istina mehanički nedohvatljiva. Za nešto više o tehničkom dijelu teorema možete pogledati raniji post. U ovom je postu prije glavnog dijela dodan rezime matematičkog dijela, a ponovljen je i argument iza osnovne filozofske posljedice.

Gödel-Rosserov teorem, filozofska i matematička strana

Matematička pozadina nepotpunosti

Kontekst su otkrića Kurta Gödela i Barkleya Rossera (tridesete godine prošloga stoljeća) u području zvanom osnove matematike. Stoga evo kratak pregled tih otkrića izbjegavajući tehničke detalje. Rezultati se odnose na klasu pogodnih matematičkih teorija. To su teorije koje su:

1. tehnički dovoljno ograničene, traži se da su u jednom smislu konačno opisive ili zahvatljive (rekurzivna prebrojivost skupa teorema), i
2. izražajno dovoljno jake, traži se da mogu dokazati sva vrlo jednostavna svojstva zbrajanja i množenja (konzistentnost i zahvaćanje primitivno rekurzivnih funkcija).

Tada bilo koji sustav koji aksiomatizira takvu teoriju sadrži tvrdnju G takvu da niti G niti ne-G nisu dokazivi. Ako ne-G nije dokaziv, kaže se i da G nije oboriv. Dakle, postoji tvrdnja (tvrdnja je “zatvorena formula”, tj. formula bez slobodnih varijabli) koja je nedokaziva i neoboriva. Ovaj teorem ćemo u nastavku zvati Gödelovim, iako je ono što je iskazano zapravo Rosserov teorem. Rosser je nadogradio Gödelov teorem slabijim i prirodnijim uvjetima na klasu teorija, ali donekle se ustalilo zvati i pojačano-pojednostavljenu verziju Gödelovim teoremom.

Dio matematičara smatra Gödelov teorem irelevantnom anomalijom zbog načina na koji se dokazuje. Konstruirana (nedokaziva i neoboriva) tvrdnja G ima jednostavnu “metamatematičku” interpretaciju (“ova tvrdnja nije dokaziva”). Ali je nejasno koje svojstvo brojeva opisuje.

Postoje prirodne nedokazive i neoborive aritmetičke tvrdnje, no za njih se uglavnom vjeruje da je njihova nedokazivost odnosno neoborivost posljedica slabosti aksioma i pravila izvođenja. Prava snaga Gödelovog argumenta je unepotpunjivost – koliko god osnažili sustav, i dalje će postojati tvrdnje koje su nedokazive i neoborive. Zbog toga je Gödelov argument teorijski bitniji rezultat od većine drugih rezultata koji daju specifične nedokazive i neoborive tvrdnje. Druge se tvrdnje obično daju riješiti dodavanjem aksioma; za Gödelov argument nedokazive tvrdnje ovise o samom skupu aksioma (G kao aritmetička formula eksplicitno ovisi o tom skupu), pa se nepotpunost ne može izbjeći trikovima poput dodavanja aksioma koji bi “pokrio rupe”.

Filozofska pozadina nepotpunosti

Gödelov rezultat ne govori ništa o istini, a i u matematici se izbjegava korištenje tog pojma. Ne zbog samog pojma istine, već jer se žele koristiti samo formalno definirani pojmovi. Obično se pod istinom u matematici misli na formalnu semantiku, u kojoj je istina matematički definiran pojam. No, Gödelov rezultat ima posljedice i za intuicije o matematičkim činjenicama. Naime, Gödelov rezultat, jer govori o aritmetici koja se slaže s našim intuicijama, neizravno govori i o intuicijama. Stoga je primjenjiv u filozofskim argumentima. Osnovna filozofska posljedica Gödelovog teorema je da ne možemo imati račun (intuitivne matematičke) istine, da postoje nedokazive i neoborive istine i neistine, odnosno da istinitost ne može biti jednaka dokazivosti. Argument iza te osnovne filozofske posljedice Gödelovog teorema je sljedeći:

1. Svaka tvrdnja o brojevima bez tzv. slobodnih varijabli je ili istinita ili neistinita. Naime, svaka elementarna formula bez kvantifikatora (uzmimo primjer “x + 0 = x”) je istinita ili neistinita kad umjesto slobodnih varijabli uvrstimo konkretne brojeve (npr. “19 + 0 = 19 ”). Kad dodamo kvantifikator (npr. “za sve brojeve x”) uz elementarne formule, dobivamo formulu (npr. “za sve brojeve x, x + 0 = x”) koja uz odgovarajuće zamjene preostalih slobodnih varijabli (drugih varijabli u našem primjeru “x + 0 = x” nema) postaje ili istinita tvrdnja – ako je redom zamjenama x sa svim konkretnim brojevima (“0 + 0 = 0”, “1 + 0 = 1”, …, “1931 + 0 = 1931”, …) dobivena istinita tvrdnja (kao u našem primjeru) – ili neistinita tvrdnja – ako je zamjenom x sa nekim konkretnim brojem dobivena neistinita tvrdnja. Svaka je matematička tvrdnja konstruirana na taj način (niz kvantifikatora nakon kojeg slijedi neka elementarna formula), i intuicija stoga govori da je svaka matematička tvrdnja ili istinita ili nije.
2. Postoji tvrdnja koja nije niti dokaziva niti oboriva (postojanje takve tvrdnje slijedi izravno iz Gödelovog teorema, štoviše Gödelov izvorni dokaz konstruira i primjer takve tvrdnje).
3. Zbog (1), u svakom paru formule F i njene negacije ne-F točno jedna je formula istinita, a druga nije.
4. Zbog (2), postoji par formula F i njene negacije ne-F takav da niti jedna od tih formula nije dokaziva (a niti oboriva).
5. Zbog (3) i (4), istinitost i dokazivost ne mogu biti sinonimi. Dvije su osnovne alternative: ne postoji intuitivna aritmetička istina (“Istina s velikim I”), ili postoji intuitivna aritmetička istina ali ju mehanički postupci ne mogu zahvatiti.

To da ne postoji aritmetička istina previše odudara od naših matematičkih intuicija. To bi značilo da, u osnovi, postoji formula poput  “a * b = c” koja za neku kombinaciju konkretnih brojeva (doduše možda jako velikih – zagovaratelji te teze bi mogli tvrditi da je veličina broja bitna, primjerice tzv. ultrafinitisti u filozofiji matematike) čini tvrdnju koja nije niti istinita niti neistinita. Stoga pretpostavimo drugu alternativu, da mehanički postupci ne mogu zahvatiti istinitost.

Razlozi i objašnjenja

Pitanje koje se tada prirodno postavlja je zašto mehanički postupci nisu dovoljni za zahvatiti istinu?. To pitanje prvenstveno traži objašnjenje Gödelove, dakle jedne matematički iskazane, tvrdnje. Iako u nekom smislu matematika može ponuditi odgovor na pitanje oblika “zašto taj-i-taj matematički teorem vrijedi?”, čini se da nam treba filozofska veza, odnosno veza intuicija i formalizma, da bismo bilo kakav matematički odgovor proglasili objašnjenjem. Zanima nas objašnjenje zašto neki teorem vrijedi u “stvarnosti”, ne “zašto neki teorem slijedi iz aksioma”. Potonji problem je posve matematički i odgovor na njega je matematički izvod. Jasno, većina ljudi će se složiti da postoje ljepši i elegantniji izvodi, i filozofija matematike može nešto reći i o tome. Ali nas zanimaju matematičke intuicije i dijelovi matematike koji su izravna formalizaija tih intuicija; konkretno (srednjoškolske) aritmetike. Moglo bi se reći da dokaz u artimetici može djelovati kao objašnjenje samo zato što je jezik matematike dovoljno blizak intuicijama da prešutno obavimo postupak vezanja intuicije i formalizma. Ali, aritmetički dokaz nikad nije doslovno i sam po sebi objašnjenje. Stoga je pitanje s početka odlomka prvenstveno filozofsko.

Jedan je odgovor na pitanje “zašto mehanički postupci nisu dovoljni za zahvatiti istinu?” ponudio Gregory Chaitin. On je kao osamnaestogodišnjak počeo rezultatima pridonositi području algoritamske teorije informacija, ranije češće znanom kao Kolmogorovljeva složenost. Koliko je u tom polju postao utjecajan najbolje govori to da je upravo on skovao naziv “algoritamska teorija informacija”. Odmah je dobro naglasiti da ona nije ničime izravno vezana uz računalstvo i računala, već uz računarstvo i računanje (napamet, na papiru, na računalu, ili drugačije – nije ključno).

No prije opisa tog područja i Chaitinovog odgovora, evo odmah što će Chaitin u osnovi  filozofski zagovarati: truthmakeri matematičkih činjenica su “kvaziempirijski”, donekle slično kao i truthmakeri činjenica o materijalnom svijetu. Što su truthmakeri? Ono što daje istinitost činjenicama neke domene. Primjerice, truthmaker pravila sporta je ljudska odluka; truthmaker moralnih vrijednosti je, ovisno o nečijim (filozofskim) vjerovanjima, racionalnost (društveni ugovor), konvencija (boo-hooray teorija morala), nepostojeć (neke verzije moralnog antirealizma), Bog (vjernici koje ne smeta Eutifronova dilema), ili nešto peto. Kvaziempirijski truthmakeri su kvaziempirijski u smislu da su bez uzorka (ne nužno bez uzroka), nisu ustrojeni ili strukturirani već su kaotični, “slučajni” i ireducibilni. Donekle je moguće aproksimirati domenu čijim tvrdnjama daju istinitosne vrijednosti, ali ne i potpuno ju zahvatiti. Primjerice, osim prirodnim znanostima, to donekle odgovara i moralnom partikularizmu. To je još jedan stav o moralnim truthmakerima prema kojem ne postoje univerzalna pravila ili metode moralno ispravnog ponašanja. Svaka situacija se stoga mora vrednovati sama za sebe, ne po tome što spada u neku veću klasu situacija u kojima je moralno učiniti to-i-to. Iako na prvi pogled uvjerljiv, partikularizam je prepun problema (npr. nemogućnost zaključivanja po analogiji). No u slučaju matematike, moglo bi se tvrditi da Chaitinovi argumenti idu u smjeru matematičkog partikularizma.

Stav da je truthmaker matematičkih istina “kvaziempirijski” ne povlači stav da su matematičke istine apstrakcija opservacija materijalnog svijeta. Niti povlači nekakvu povezanost (osim nekih zajedničkih teorijskih svojstava) fizike ili biologije s matematikom. Chaitin se, istini za volju, ne bi bunio na tvrđenje takve povezanosti, no ovdje je fokus na njegovo objašnjenje problema veze istinitosti i dokazivosti, ne na Chaitinovu sliku svijeta.

Za predstaviti Chaitinov filozofski pogled potrebni su neki pojmovi iz algoritamske teorije informacija.

Algoritamska teorija informacije (AIT)

String je konačan proizvoljno dugačak niz znakova nastao nadovezivanjem simbola jednog na drugi iz prethodno dogovorene (konačne) abecede. Svako slovo, riječ, rečenica ili tekst hrvatskog (i engleskog) jezika su stoga stringovi. Zatim, i svi su brojevi u dogovorenom brojevnom zapisu stringovi.

Ljudi imaju intuiciju da su neki stringovi složeniji odnosno jednostavniji od drugih. Primjerice, “111 111” bismo proglasili jednostavnijim od “101010”, kojeg bismo proglasili jednostavnijim od “100 110”.

(Klasična) teorija informacije je formalizam za zaključivanje s tzv. ekstrinzičnom količinom informacije. Primjerice, jedno klasično pitanje na koje teorija informacije može dati odgovor je “ako imam veliku bazu rečenica na hrvatskom jeziku, koliko je vjerojatno da u nasumično izabranoj rečenici nakon što sam pročitao/la ‘Dobar ’ slijedi ‘dan’?”. Možemo (uz dozu traljavosti) povezati pojam vjerojatnosti i pojam jednostavnosti i proglasiti pojmove poput entropije odgovornima za intuitivne pojmove jednostavnosti (kao što je popularno raditi u popsci industriji).

No, čak ni tada teorija informacije ne daje odgovor na pitanje poput “je li 111111 jednostavniji string od 101011?”, ako to pitanje ne kvalificiramo nekakvim pretpostavkama. Odnosno, teorija informacije ne daje mogućnost govora o intrinzičnoj jednostavnosti stringa. Ovo, usput, nije nikakav problem za teoriju informacije – njen je cilj (ne računajući popularnu literaturu) posve praktičan, ne filozofski.
Jedan od osnovnih rezultata klasične teorije informacije je Huffmanovo kodiranje, kojim se izvorno povećala efikasnost opterećenja telefonskih mreža. Ljudi neke zvukove ispuštaju češće nego duge, pa su češći zvukovi kodirani kraćim kodom u telefonskoj mreži. Huffmanovo kodiranje je asimptotski optimalno kodiranje koje koristi spomenutu ideju te rezultate iz teorije informacija; optimalno uz uvjet da je korištena dovoljno dobra statistika o ljudskom govoru.

Algoritamska teorija informacije, s druge strane, formalizira (ili barem pokušava formalizirati) intrinzičnu količinu informacije nekog stringa. Dakle, AIT govori o intrinzičnoj količini informacije, dok klasična teorija informacije govori o relativnoj (ekstrinzičnoj) količini informacije.

Osnova AIT je funkcija (pridruživanje, preslikavanje) K koje svakom stringu pridružuje pozitivan cijeli broj. Taj broj predstavlja duljinu najkraćeg opisa stringa, što bi u idealnom slučaju (npr. u slučaju postojanja hipotetskog mentalnog jezika mentalese) trebalo odgovarati pojmu jednostavnosti. Sad se postavljaju pitanja:

1. Što je “opis”? I u slučaju da postoji više “vrsta opisa”, kako AIT, odnosno funkcija K, odabire specifičnu vrstu opisa?
2. Kako “radi” (kako se “računa”) funkcija K? Tj. ako imamo neki string poput 101101, kako izračunati njegovu (intrinzičnu) složenost?

Opis je niz rečenica u fiksiranom jeziku (ubrzo ćemo vidjeti kako i zašto fiksiranom). S obzirom na to da je AIT matematička teorija, trebaju nam strogo definirana sintaksa i semantika jezika opisa. Kako stvari stoje, tako striktno su u ovom trenutku definirani samo programski jezici. Opet je dobro ponoviti da AIT nije vezan uz računala. Niti programski jezici općenito nisu jezici “računala” niti ih računalo razumije ili može izvršavati. Istina je da se opisi napisani u programskom jeziku najčešće mogu pretvoriti u opis s kojim računalo može baratati. No programski su jezici izmišljeni za ljude, a njihova je eventualna težina korištenja prvenstveno u tome što ljudi inače nisu primorani pisati jednoznačno i egzaktno. Programski jezici zapravo olakšavaju posao jer nude egzaktnu sintaksu i semantiku – pisati programe (opise) u prirodnom jeziku je noćna mora (što zna svatko tko je pokušao izraziti nešto kompliciranije u Wolfram Alphi ili sličnom interpreteru prirodnih jezika). U osnovi, tri su tipa opisa. Prva dva dolaze iz matematike, no treći je ipak (zasad) popularniji:

1. Deklarativan opis. Primjerice, opis operacije množenja u Peanovoj aritmetici (koja je, spomena radi, jedna od onih teorija na koju se odnosi Gödelova nepotpunost). U Peanovoj aritmetici postoje tvrdnje “za svaka dva broja a i b, a * (b + 1) je isto što i a * b + a”, te “za svaki broj a, vrijedi a * 0 = 0”. Taj opis u potpunosti definirana ponašanje množenja.
2. Funkcijski opis. I ova se vrsta opisa koristi u matematici, pa i (iako ne potpuno izravno) u Peanovoj aritmetici. U školama se operacija faktorijela uvijek definira funkcijskim opisom. No ostanimo na primjeru množenja: “umnozak(a, b) = umnozak(a, b – 1) + a ako je b > 0” te “umnozak(a, b) = 0 ako je b = 0”.
3. Imperativan opis. Množenje bismo mogli ovako definirati: “umnozak(a, b) = { Postavi rješenje na 0; Ponovi b puta: { Uvećaj rješenje brojem a; }; Ispiši rješenje; }.”. Nećemo ih koristiti u nastavku, ali spomenimo Turingove strojeve. Iako se na prvi pogled ne čini tako (jer se zadaju deklarativnim pravilima ponašanja), Turingovi su strojevi zapravo metoda imperativnog opisa jer pravila kojima se zadaje jedan Turingov stroj daju potpun postupak dolaženja do rješenja, ne samo (makar i jednoznačnu) karakterizaciju rješenja kao što je slučaj s prethodna dva tipa opisa. Primjerice, deklarativan opis ne daje baš nikakvu eksplicitnu informaciju o tome kako izračunati 2 * 3.

Imperativni opis daje najbolji osjećaj potpunosti specifikacije procesa koji se opisuje, pa je (barem što se intuicija tiče) najprikladniji za AIT. Pojam “algoritam” kao metode rješenja nekog problema se prirodno veže uz imperativni tip opisa. Zbog toga i naziv “algoritamska teorija informacija”.

No, koji tip imperativnog opisa koristiti? Tj. ako imamo string “110101”, u kojem jeziku trebamo tražiti najkraći opis? Postoje tisuće imperativnih programskih  jezika (i beskonačan skup mogućih jezika). Velik i važan rezultat u samim temeljima AIT je: u nekom smislu je svejedno koji tip imperativnog opisa odaberemo!

Ne baš doslovno svejedno. Primjerice, semantika nekog jezika može definirati da nekakva naredba “IspisiVelikiBroj;” ispisuje prvih 1000 znamenki decimalnog zapisa broja PI. Usput, prešutno pretpostavljamo očito plauzibilan zahtjev da ne postoje semantike koje definiraju nemoguće (ili neočite) postupke poput “ispiši je li ova tvrdnja intuitivno istinita ili nije, za proizvoljno danu tvrdnju”, ali ispis decimala PI je moguć i teorijski lagan zadatak. Može se strogo i jednostavno definirati kakve jezike, odnosno sintakse i semantike dopuštamo. No ulaženje u tu temu ne bi pridonijelo temi ovog posta. U većini drugih jezika, koji ne sadrže ekvivalent naredbe “IspisiVelikiBroj;”, za postići ispis prvih 1000 znamenki decimalnog zapisa broja PI morat ćemo (recimo) prvo definirati nekakvu funkciju koja aproksimira PI na proizvoljnu točnost, te potom zatražiti od te funkcije točnost od 1000 decimala. Dakle, u prosjeku mnogo više simbola od petnaestak.

U kojem je onda smislu svejedno koju vrstu opisa (jezik) odaberemo? Vrijedi sljedeća tvrdnja (argument zašto vrijedi je u idućem odlomku). Neka su J1 i J2 izražajno dovoljno snažni – traži se zapravo vrlo malo izražajne snage – imperativni jezici sa strogo definiranom sintaksom i semantikom. Neka su K1 i K2 funkcije koje svakom stringu pridružuju duljinu najkraćeg J1-opisa, odnosno duljinu najkraćeg J2-opisa. Tada vrijedi: K1(x) < K2(x) + c(J1, J2). Izraz c(J1, J2) je konstantan broj (obično i vrlo mali) ovisan o odabranim jezicima J1 i J2, ali neovisan o stringu x. Dakle, razlika u minimalnoj veličini opisa neka dva jezika je unutar neke konstante. Ako biste gledali graf  na kojem su nacrtane i funkcija K1 i funkcija K2, te ako biste dovoljno “odzumirali” sliku, linije koje predstavljaju K1 i K2 bi se vizualno poklopile u “jednu” liniju koja bi jednako rasla, padala, “skakala”, ili što već.

Argument iza ove tvrdnje je jednostavan: U jeziku J1 možete napisati tzv. interpreter jezika J2. Tj. možete napisati J1-opis koji će (1) sadržavati opis simulacijskoj procesa koji kao ulaz prima J2-opise te ih izvršava simulirajući semantiku jezika J2, te (2) iskoristiti upravo spomenuti opis simulacije sa najkraćim J2-opisom kao argumentom. Stoga je izraz c(J1, J2) otprilike jednak duljini opisa simulacijskog procesa, te duljini sintakse za “poziv” tog simulacijskog procesa. Izraz K1(x) je stoga manji od c(J1, J2) uvećanom za veličinu J2-opisa (koji je minimalno veličine K2(x)).

Imajući na umu argument o simulaciji, odnosno tvrdnju iz pretprethodnog odlomka, možemo fiksirati neki jezik i konkretnu složenost izražavati preko tog jezika. Obično se uzima neka verzija Turingovog stroja – ali ovdje ćemo koristiti hrvatski jezik (uz aritmetičke operatore) čije ćemo nejednoznačnosti i druge probleme prirodnih jezika zanemariti.

Sad treba odgovoriti na pitanje “kako se računa K(x) ako znamo samo kako izgleda string x?”. Pogledajmo prvo primjer. Primjeri će biti stringovi koji predstavljaju brojeve u dekadskom zapisu, no jednako ima smisla pitati i primjerice “Koliko je K(Kurt Gödel)?”, samo što je tada teže demonstrirati svojstva koja nas zanimaju. Koliko je K(2)? Najkraći opis bi bio Ispiši 2. Stoga je K(2) = 9. To nije osobito zanimljivo. Koliko je K(10000)? Rješenje Ispiši 10^4. je kraće od rješenja Ispiši 10000. Ako je prvo rješenje i najkraće s obzirom na skup operatora koje smo fiksirali (to nismo definirali, ali zamišljamo da jesmo), onda je K(10000) = 12.

Možda već naslućujete problem: jako je teško odrediti najkraći opis danog stringa. Nažalost, općenito je to i nemoguće. Ovo bi trebalo biti iznenađujuće: znamo da za string x duljine n najmanji opis sigurno nije dulji od n + 8 znakova (8 znakova nam treba za Ispiši, razmak i točku, dok ostatak prepuštamo eksplicitnom navođenju stringa x duljine n). Zašto ne bismo onda pretražili sve moguće opise od kraćih prema duljima (do duljine n + 8), takvih opisa je samo konačno mnogo  – red veličine dva na (n + 8) – pogledali što ispisuju, i zaustavili postupak kad naiđemo na prvi opis koji ispisuje željeni string x?

Problem je u tome što neki opisi opisuju postupke koji se ne zaustavljaju. Primjerice Dok vrijedi (1 > 0): {Ispiši 1; }. U ovom slučaju je očito da se proces ispisivanja jedinica ne zaustavlja (jer je 1 (za)uvijek veći od 0). Kad bi to uvijek bilo očito (ili makar bilo kako uočljivo), mogli bismo eliminirati opise beskonačnih procesa iz pretrage. Nažalost, temeljni rad u području izračunljivosti kaže da ne postoji metoda za detekciju završava li ikad proces koji slijedi dani opis ili ne. Za tematski bliske primjere kako izgleda opis procesa za koji nije trivijalno (a možda je i nemoguće) dokazati da ne završava, možete potražiti definicije tzv. busy beaver programa za koje se zasad ne zna završavaju li. Dakle, do sada uvedenom terminologijom, ni za koja dva (možda ista) jezika J1 i J2, ne postoji J1-opis postupka koji za proizvoljni ulazni J2-opis ispisuje “da” ako proces opisan J2-opisom staje, odnosno “ne” ako ne staje. Ova činjenica je inače poznata kao nerješivost halting problema, i osnovni je rezultat matematičke teorije računanja.

To što je pokušaj računanja K(x) metodom pretrage opisa propao, ne znači da se K(x) općenito ne može izračunati, samo da se ne može izračunati na taj način (pretragom konačnog broja opisa unutar kojih se sigurno nalazi i najmanji). Nažalost, K(x) se doista općenito ne može izračunati. To znači da, osim nekih slabih donjih i gornjih granica, za većinu dovoljno velikih stringova ne znamo kakva im je složenost.

To je demoralizirajuć rezultat koji zbog tehničkog i neintuitivnog dokaza nećemo argumentirati, ali nije poguban za AIT. Neizračunljivost nije isto što i “besmisleno” ili “nedovoljno strogo definirano”. Matematičke funkcije su svakakve, jedna vrlo mala klasa funkcija koje postoje u aktualnim teorijama skupova (teorija skupova između ostalog određuje kakve funkcije postoje) je izračunljiva, ostatak nije. Gotovo cijela matematika realnih brojeva je neizračunljiva (osim jednog, u jednom preciznom smislu beskonačno malog, dijela).

Postojanje neizračunljivih funkcija nije problem za matematiku, već za ljude, odnosno eventualno filozofiju matematike. Slično kao što u filozofiji matematike dio ljudi (većina?) zagovara postojanje samo potencijalne beskonačnosti, tako i dio ljudi zagovara postojanje samo izračunljivih funkcija. To nema veze s korištenjem aktualne beskonačnosti, odnosno neizračunljivih funkcija, u samoj matematici (ne filozofiji matematike), jer se matematičar ne obavezuje na vjerovanje u ontologiju teorije koju koristi, kao ni na izjednačavanje ontološkog statusa objekata o kojima govori; primjerice partitivnog skupa prirodnih brojeva (kao primjer egzotičnog i-više-nego aktualno beskonačnog objekta) i broja 3 (kao primjer objekta u kojeg svi vjeruju, u ovom ili onom smislu). U kontekstu pitanja kojima se bavi ovaj post jesu bitni filozofski stavovi oko izračunljivosti, jer se bavimo filozofskim problemom, ali pojam “najkraćeg opisa” djeluje dovoljno nedužno da se ne zaustavimo na tom pitanju.

Ako za string vrijedi da je “K(x) > |x|”, gdje je |x| duljina stringa x, tj. da je minimalni opis stringa otprilike jednako dugačak kao i eksplicitno navođenje samog stringa, onda taj string možemo zvati algoritamski slučajnim (ireducibilnim). On je slučajan utoliko što nema pravilnosti, nema obrasca kojim bismo mogli komprimirano opisati njegovu konstrukciju. Za proizvoljan prirodan broj postoji daleko više stringova nego što je valjanih opisa (npr. iSpIšI 123?! nije valjan opis), iz čega jednostavnim kombinatoričkim argumentom slijedi da je većina stringova slučajna. Slučajnost nekog stringa naravno ovisi o fiksiranom jeziku. Ima smisla govoriti o zaista slučajnim stringovima ako fiksiramo jezik. Ako ne fiksiramo jezik, ima smisla govoriti o zaista slučajnim nizovima: to su nizovi u kojima su svi konačni početni komadi u svakom jeziku, osim možda konačno mnogo takvih konačnih početnih komada, slučajni. Naravno, sve to ako se složite da je nemogućnost kompresije eksplicitnog opisa vezana uz intuitivnu ideju slučajnosti (shvaćenu u smislu engleskog random, možda više “nepredvidljivo” nego “slučajno”).

Nepotpunost iz složenosti

Chaitin je dokazao sljedeći teorem. Neka je T proizvoljna pogodna teorija aritmetike (v. početak posta za neformalan opis pogodne teorije). Tada za neku duljinu L0, ni za jedan n veći od L0 i ni za koji x nije dokazivo “K(x) > n”. Pritom su x i n brojevi. Broj x predstavlja npr. ASCII ili drugi brojevni kod stringa x (a ne sam string x, jer stringovi nisu intrinzično dio Peanove i sličnih aritmetika, srećom daju se simulirati kodovima), a n je prirodan broj. Ovo dijelom slijedi  iz činjenice da je “K(x) > n” općenito neodlučiva tvrdnja; kad bi za sve stringove x bilo dokazivo “K(x) = cx”, gdje je cx najmanja duljina programa koji ispisuje x, onda bi sve tvrdnje oblika “K(x) > n” bile odlučive čim pronađemo dokaz za “K(x) = c” za bilo koji c veći od n.

Već je argumentirano da je smisleno (iako neizračunljivo) za svaki string govoriti o najkraćoj duljini opisa. Stoga, Chaitinov argument pokazuje da postoji beskonačno mnogo istinitih, ali nedokazivih, formula. To su dakle formule koje izražavaju da je specifičan string slučajan (K(x) > |x|), za beskonačno mnogo specifičnih stringova.

Chaitin je objavio gomilu (nažalost ne baš pažljivo pisanih) članaka i knjiga koje promiču njegove filozofske ideje. Koristit ćemo citate njegovog članka Gödel’s Theorem and Information. Krenimo s citatima dijelova koji su već komentirani u postu, ovaj put Chaitinovim riječima. (moj prijevod – donekle slobodan)

(…) tradicionalni dokazi Gödelovih teorema nepotpunosti [postoji još jedan Gödelov teorem nepotpunosti osim onog s početka teksta, taj drugi je na temu dokazivanja konzistentnosti skupa aksioma, filozofski manje bitan] pokazuju da su formalni aksiomatski sustavi nepotpuni, ali ne pružaju metodu mjerenja dokazne snage sustava, odnosno rangiranja [teorija] po stupnju potpunosti ili nepotpunosti.

AIT se fokusira na individualne objekte radije nego na skupove i vjerojatnosne distribucije u Shannonovoj (…) teoriji informacije. Koliko bitova nam treba da opišemo kako izračunati individualni objekt?

A sad nešto novo. Realan broj je algoritamski slučajan ako je za opis njegovih prvih n decimala (nakon nekog početnog komada od m decimala) potreban opis duljine veće od n.

Kako bih nastavio, moram definirati algoritamski slučajan realan broj Ω (…). Ω je prikladan za štovanje u mističkim kultovima jer (…) u određenom smislu sadrži svu matematičku istinu te ju izražava na najkoncizniji i najkompaktniji način. Znati n-ti bit Ω je ekvivalentno znanju koji procesi čiji su opisi duljine manje od n završavaju a koji ne. Ω je definiran kao vjerojatnost završavanja procesa slučajno odabranog opisa (…), ako je svaki bit [opisa] tog procesa odabran nezavisnim bacanjem poštenog novčića.

Znanje Ω (za neke upotrebe čak i samo konačnog ali relativno dugog početnog komada decimala) bi riješilo pitanje “je li dana formula teorem primjerice Peanove aritmetike?”. Naime, mogli bismo se pitati “hoće li proces koji pretražuje sve moguće dokaze (nizove formula), te stane kad pronađe dokaz naše tvrdnje, ikad stati?”. Ako je odgovor “da” odnosno proces staje, očito je tvrdnja dokaziva, inače nije. To bi, između ostalog, učinilo nepotrebnim velik dio ručnog matematičkog posla u teoriji brojeva. Vrijedi spomenuti da taj pristup pretraživanjem dokaza ne bi uključivao rješenje (intuitivne) istinitosti neke specifične nedokazive i neoborive aritmetičke tvrdnje, jer za nju već znamo da je nedokaziva i neoboriva (tj. nije teorem, niti je njena negacija teorem).

Ali, čini (mi) se da bismo mogli ispitivati i intuitivnu istinitost aritmetičke formule, što je bitno teži od problem od ionako neizračunljivog problema “je li dana formula teorem u Peanovoj aritmetici?”. Naime, ako imamo formulu oblika “za svaki x, [ostatak formule]”, upitamo naš Ω-informiran algoritam “staje li proces koji traži protuprimjer [ostatku formule]?” (ako da: postoji protuprimjer i cijela tvrdnja ne vrijedi, inače vrijedi), a potom Ω-informiran algoritam to isto radi na ostatku formule (ima samo konačno mnogo kvantifikatora, a elementaran dio formule bez kvantifikatora je izračunljiv i bez Ω).

Sve te lijepe posljedice poznavanja decimala Ω ukazuju na to da je konstanta Ω predobra da bi bila izračunljiva. U nekom smislu je i bespredmetno govoriti “što bismo mogli računati kad bismo znali Ω” jer je antecedent (znanje decimala Ω) nužno nezadovoljen.

Ipak, evo još malo o  Ω, konkretno jedan zanimljiv rezultat koji veže udaljene dijelove matematike:

Ω se također može predstaviti polinomom sa stotinjak varijabli, sa cijelobrojnim koeficijentima i eksponentima. n-ti bit  Ω [u binarnom zapisu] je tada 1 ako i samo ako postoji beskonačno mnogo prirodnih brojeva k takvih da jednadžba P(n, k, x1, …, x98) = 0 ima rješenje u prirodnim brojevima.

Zatim filozofskiji dio:

[Algoritamska] teorija informacija sugerira da je Gödelov fenomen prirodan i široko rasprostranjen, ne patološki i neobičan.

Chaitin cilja na to da nije samo rečenica G (i njene trivijalne istinitosno funkcionalne varijante) nedokaziva i neoboriva u svakoj pogodnoj aritmetičkoj teoriji, već beskonačno mnogo rečenica o (algoritamski) slučajnim brojevima: znamo da su skoro svi brojevi (stringovi) slučajni, a samo je za konačan dio brojeva (kodova stringova) dokazivo da su slučajni.

Malo o filozofiji matematike:

(…) je li [stoga] Gödelov teorem poziv na revoluciju i anarhiju? (…) Može li netko odustati od dokazivanja teorema nakon dva mjeseca i naprosto ga dodati kao aksiom? (…)

Novi aksiomi bi se trebali birati s pažnjom, zbog njihove plodnosti i velikog broja argumenata da su ispravni, na sličan način kao u zajednicama empirijskih disciplina.

Slijedi nekoliko citata iz “Meta Math!”, još jedne Chaitinove publikacije.

Prvo, neki Chaitinovi stavovi o filozofiji matematike. Vrijedi dati barem obrise Chaitinovih stavova. Prema kraju ovog niza stavova sve je više kontroverznih stavova – mnogi se filozofi i matematičari ne bi složili. (moj poredak i prijevod, ponovno donekle slobodan)

Matematika je način izražavanja ili karakterizacije struktura. (…)

Da bi preživjele, matematičke ideje moraju biti lijepe, zavodljive, prosvjetljujuće, moraju nam pomoći da razumijemo, moraju nas inspirirati. (…)

Pogreška je misliti da matematičke teorije preživljavaju samo zato što (…) imaju praktične upotrebe. Naprotiv, što je korisno je funkcija vremena, dok vrijedi a thing of beauty is a joy forever (Keats). (…)

U kreativnom matematičkom procesu, matematičari koriste intuiciju i smisao za estetiku (…), ne vode logičke mehaničke “racionalne” živote. (…)

Matematika je daleko od statičnosti i perfekcije; ona se konstantno razvija (…) u nove oblike.

Chaitin je inače veliki fan Leibniza, na početku knjige “Meta Math!” je i ovaj zanimljiv citat (dan u izvornoj i engleskoj varijanti):

Sans les mathématiques on ne pénétre point au fond de la philosophie.
Sans la philosophie on ne pénétre point au fond des mathématiques.
Sans les deux on ne pénétre au fond de rien.

Without mathematics we cannot penetrate deeply into philosophy.
Without philosophy we cannot penetrate deeply into mathematics.
Without both we cannot penetrate deeply into anything.

Chaitin tvrdi kako je izvor njegovih ideja o složenosti i ireducubilnosti (algoritamski slučajni brojevi) upravo kod Leibniza. Zanimljivo, Chaitin (nadajmo se većim dijelom u šali) tvrdi da Leibniza može razumjeti samo netko tko je intelektualno napredovao kao Leibniz – a to je, nastavlja Chaitin, upravo on sam, pronalaskom veze nepotpunosti i zaista slučajnih brojeva.

Neovisno o tome šali li se Chaitin u ovakvim izjavama ili ne, njegov stil pisanja zna biti senzacionalistički. Ako se tko upusti u čitanje Chaitina, možda je ovo dobro mjesto za predložiti usporedno čitanje udžbenika An Introduction to Kolmogorov Complexity and Its Applications (Ming Li i Paul Vitanyi) kao sadržajniji uvod u AIT koji uključuje i dokaze Chaitinovih teorema. Nažalost, u tom udžbeniku nema puno spomena filozofskih posljedica, pa u ovom tekstu nema citata iz tog udžbenika. No, vratimo se na temu.

Chaitin se dakle poziva na Leibniza kao ideološki izvor svojih otkrića. Jedna od Chaitinovih ideja je da složenost posljedica proizlazi iz složenosti uzroka. S tehničke strane to opravdava činjenicom da složenost aksioma teorije daje gornju granicu na složenost njenog skupa teorema. Odnosno, filozofskijim terminima (koje Chaitin ne koristi), možda bismo mogli reći da Chaitin smatra kako složenost (i posljedično dokazna nedohvatljivost) matematičke istine proizlazi iz složenosti njenog truthmakera.

Leibniz (po Chaitinovom shvaćanju) vjeruje u početni uzrok (“Boga”) jer vjeruje da je svijet nastao (imao početak), i vjeruje da je složenost posljedice sadržana u uzroku. Ovo bi bio svojevrsni novi argument za (naravno, filozofskog) Boga: Bog postoji jer postoji složenost u svijetu.

Chaitin vidi, mora se priznati osnovanu, daljnju poveznicu Leibniza i svojih stavova. Interpolacija je proces kojim se od niza opažanja može dobiti teorija. U filozofiji znanosti je dobro poznat jednostavan matematički rezultat da za svaki ljudski skup opažanja  postoji beskonačno mnogo nekompatibilnih teorija nastalih intepolacijom koje jednako dobro objašnjavaju skup opažanja kojeg interpoliraju (ne nužno i neko novo opažanje). Naime, broj opažanja je uvijek konačan, a teorije se formuliraju funkcijama koje imaju neograničenu domenu mogućih ulaznih podataka. Kako onda odabrati jednu teoriju? Specifično, kako odabrati teoriju koja je “zakon prirode”, koja je doista istinita, ne samo prikladna? Chaitin parafrazira Leibniza:

Ako je zakon [teorija] iznimno kompliciran, onda su točke slučajne, onda su iregularne i nisu u skladu sa zakonom prirode. Ali ako je zakon jednostavan, onda je to doista zakon prirode, nismo se prevarili!

Dakle, ispravna teorija je ona koja jednostavno opisuje opažanja. Jednostavnost je, kaže Leibniz, i signal da smo zahvatili pravi prirodni zakon, ne samo praktični kriterij koju teoriju odabrati. I na to se nadovezuje Chaitin: za takvu filozofiju znanosti nam treba još samo mjera jednostavnosti teorije, a to je upravo AIT složenost opisa te teorije, odnosno vrijednost funkcije K aksioma te teorije.

Gödelov teorem odnosno (njegovo oslabljenje s potencijalno intuitivnijim posljedicama) Chaitinov teorem ukazuju, smatra Chaitin, na to da je svijet brojeva i njihovih odnosa previše složen – potpuna (matematički nedefinabilna) teorija istinite aritmetike je barem dijelom zaista slučajna, ireducibilna. Truthmaker aritmetike, što god on metafizički bio, je presložen da bi se zahvatio konačnim metodama (algoritmima). Zato imamo nedokazive i neoborive rečenice.

Još malo o Ω:

Uobičajeno poimanje matematike je potraga za strukturom i zakonima u svijetu matematike, potraga za teorijom. Ali teorija implicira kompresiju, a ovdje [konstanta Ω] ne može biti nikakve [kompresije] – nema nikakve strukture ni zakona u ovom konkretnom kutu svijeta matematike.

Chaitinov slijed misli dovodi do zanimljivog zaključka: zašto su matematičke istine istinite? Nema razloga! Ili možda točnije – nema objašnjenja, istine su istinite same po sebi; njihova istinitost je primitivna činjenica (matematičkog – a onda i našeg) svijeta. Svaki razlog (objašnjenje) je, prema Chaitinu, kompresija, pronađena zakonitost. Ako nema zakonitosti, nema ni razloga. Aritmetičke istine su istinite i – to je sve što se može reći. Pri kraju knjige Chaitin komentira da je slučajnost doista nezgodan odabir riječi i da bi bolji izbor bio “ireducibilnost”.

Što je posljedica ovakvog pogleda na matematiku? Svakako je jedna velika posljedica potreba za manje formalnim, odnosno kvaziempirijskim istraživanjem matematike. Ako je truthmaker matematike doista ireducibilan (slučajan, odnosno uglavnom ga se ne može komprimirati), onda nam formalni sustavi daju tek mali dijelić matematičke istine. Chaitin stoga kaže:

Formalni aksiomatski sustavi su promašaj! Sustavi dokazivanja teorema ne funkcioniraju. Možemo objavljivati članke o njima, ali oni dokazuju samo trivijalne teoreme.

Čini se da je ovo nepotrebno tragičan pogled na formalizme; ako je Chaitinov pogled i točan, treba tek pokazati da postoje zanimljive matematičke istine koje izlaze iz okvira formalizama.  Broj Ω i njegova svojstva su zanimljivi filozofima i (meta)matematičarima, ali slično kao i Gödelovi teoremi, ne govore nešto što bi bilo strašno zanimljivo prosječnom matematičaru. Dakle, tek treba pronaći zaista zanimljive i u nekom smislu apsolutno presložene matematičke istine.

Što kažu drugi?

Čini se da je većina filozofa na strani toga da Chaitinove filozofske tvrdnje nisu dovoljno uvjerljive. Tu odmah treba reći da Chaitinovi argumenti nisu na niskoj razini, primjerice, Rogera Penrosea (Gödel, um i strojevi) ili Sama Harissa (slobodna volja i determinizam), dvojice znanstvenika (s doduše i filozofskim obrazovanjem) koji su filozofiju počastili katastrofalnim argumentima, ali argumentima koji su postali popularni zbog puke popularnosti autora u njihovim područjima fizike odnosno neuroznanosti. Kao i oni, Chaitin također nije profesionalan filozof.

Radije, za Chaitinove argumente se čini da ostavljaju preveliku rupu u argumentima (non sequitur), no ipak daju jedinstven i svjež pogled na problematiku. Pređimo na argumente i pogledajmo neke klasične prigovore, preuzete iz članka Algorithmic Information Theory autora Michiela van Lambalgena, inače uglednog nizozemskog filozofa i logičara. Spomenuti članak je javno dostupan na Internetu – ako želite znati više o AIT, a ranije spomenuti udžbenik An Introduction to Kolmogorov Complexity and Its Applications (Ming Li i Paul Vitanyi) Vam je predugačak, u ovom se članku daju gusti ali ipak razumljivi (razumljivi barem u otprilike prvoj trećini članka) dokazi temeljnih rezultata iz područja AIT i primjene na teoreme nepotpunosti.

Prvi se prigovor odnosi na činjenicu da Chaitinov dokaz ne daje eksplicitan izgled nedokazive istine. Sjetimo se Chaitinove izjave:

[Algoritamska] teorija informacija sugerira da je Gödelov fenomen prirodan i široko rasprostranjen, ne patološki i neobičan.

Iako znamo da, za razliku od Gödela i samo jedne nedokazive istine G, Chaitinov dokaz pokazuje da postoji beskonačno mnogo (logički neistovrijednih) nedokazivih istina, mi zapravo ne znamo niti jedan konkretan primjer takve rečenice – u tom smislu su Chaitinove rečenice zapravo još manje potencijalno korisne našim intuicijama od Gödelove neprirodne ali eksplicitno konstruirane G. Za Chaitinove rečenice znamo kakvo svojstvo izražavaju (taj-i-taj broj je zaista slučajan), ali ne znamo kako izgleda. Za G ne znamo o čemu priča u kontekstu teorije brojeva, ali znamo kako izgleda.

Odgovor prigovoru? Čini se da klasičan matematičar (u opreci s konstruktivistom, v. idući odlomak) ne bi trebao imati problema s time što ne znamo konkretnu istinu oblika “K(x) > n”. Znamo da takve rečenice postoje, i smeta nas to što postoje, i što su gotovo sve rečenice tog oblika istinite i nedokazive. Nejasno je kakvu bi informaciju donijelo primjerice to da je “K(prvih milijun znamenki baze prirodnog logaritma) > 1931” nedokaziva istina. Bilo bi zanimljivo moći konstruirati takvu tvrdnju, no to se ne čini presudnim. S druge strane, konstruktivist će odbaciti kompletan Chaitinov dokaz, pa onda i navodne intuicije koje on donosi. Zanimljivo, Gödel-Rosserov dokaz je provodiv i za Heytingovu aritmetiku, konstruktivističku analogiju Peanovoj aritmetici

(Osnovna razlika klasične i konstruktivističke matematike je odbacivanje valjanosti načela “ako iz ne-P slijedi kontradikcija, onda vrijedi P” – ali, za razliku od zanimljivo rasprostranjenog pogrešnog mišljenja, konstruktivisti će se složiti da vrijedi “Ako iz S slijedi kontradikcija, onda vrijedi ne-S”, kao i da vrijedi “ako iz ne-P slijedi kontradikcija, onda vrijedi ne-ne-P”, dakle problem čini dvostruka negacija; vrijedi spomenuti i da konstruktivisti ne smatraju da je klasična kontradikcija ponekad konzistentna, već radije da su tvrdnje oblika “P ili ne-P”, što je za njih zapravo “dokazivo je: P ili ne-P” “istinite” tek onda kad imamo ili “dokazivo je P” ili “dokazivo je ne-P”.)

Sljedeći se prigovor odnosi na činjenicu da je količina informacije teorije (koja se shvaća kao duljina najkraćeg opisa procesa koji izlistava sve teoreme) slabo vezana uz duljinu n za koju niti jedna tvrdnja oblika “K(x) > n” nije dokaziva. Chaitin na više mjesta aludira da se teorije mogu rangirati prema svojoj složenosti, no pokazuje se da je veza minimalnog takvog n – dakle n za koji niti jedna tvrdnja oblika “K(x) > n” nije dokaziva – i vrijednosti K(opis teorije) slaba. Preciznije, pod “slabo” se misli da te dvije veličine nisu uvijek udaljene do na neku konstantu. Chaitin bi vjerojatno na to rekao da se slaže i prešao na slabiju varijantu svoje teze, da K(opis teorije) daje jednu (slabiju) gornju granicu na složenost teorema teorije. O ovom problemu govori i Panu Raatikainen u On Interpreting Chaitin’s Incompleteness Theorem (također javno dostupan članak). Ipak, taj je problem nekako najmanje relevantan za našu temu: poanta je bila istražiti uzroke unepotpunjivosti aritmetike. Također, čini se da Raatikainen smatra da je problem s Chaitinovom interpretacijom u stupnju posljedica, ne u tome da su Chaitinovi tehnički rezultati zapravo filozofski irelevantni (moj prijevod):

Unatoč svemu, ne mislim da moje konkluzije impliciraju da Chaitinov teorem nepotpunosti nije zanimljiv rezultat. Osobno smatram da jest [zanimljiv], samo što je pogrešno shvaćen.

Treći i možda najbitniji van Lambalgenov prigovor je on sam izvrsno formulirao, pa slijedi njegov citat (moj prijevod i podebljavanje):

Nema ništa u teoremu [Chaitinovoj verziji nepotpunosti] što bi podržalo Chaitinovu tvrdnju da je neodlučivost formule posljedica preobilja informacijskog sadržaja. Primijetite da [u Chaitonovom dokazu] nismo ništa rekli o informacijskoj složenosti samih [neodlučivih] formula oblika “K(x) > c” (što god to značilo), bilo je važno samo da određena formula tvrdi da određen string sadrži višak informacija, što je nešto posve drugačije.

Nisam uspio pronaći Chaitinov odgovor ovom van Lambalgenovom argumentu. Mogući odgovor bi bio da formula “K(x) > c” gledana kao string ovisi o složenosti stringa x (što, ako i jest točno, nije očito, jer sjetimo se da formule sadrže brojevne kodove a ne prave stringove). Bio Chaitin u pravu po tom pitanju ili ne, Chaitinova interpretacija nudi nove poglede na problem nepotpunosti. Možda ti novi pogledi nisu toliko revolucionarni koliko bi Chaitin htio, no, a s čime se slaže i ranije citirani kritičar, zanimljivi su. Kratki sažetak ideja: mehanički nezahvatljivi truthmakeri, veza s Leibnizom i komprimiranjem opažanja, veza s filozofijom znanosti i kriterijem jednostavnosti te Chaitinov kvaziempirizam.

Popis literature.

• (preporuka) Ming Li i Paul Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. 3. izdanje. Springer-Verlag, New York.
• Gregory J. Chaitin. Meta Math!: The Quest for Omega. Vintage, New York.
• Gregory J. Chaitin. Gödel’s theorem and information. U: International Journal of Theoretical Physics. 21(12). Stranice 941-954.
• Michiel Van Lambalgen. Algorithmic Information Theory. U: Journal of Symbolic Logic. 54(4). Stranice: 1389-1400.
• Raatikainen, Panu. On interpreting chaitin’s incompleteness theorem. U: Journal of Philosophical Logic. 27(6). Stranice: 569-586.