Drugi Gödelov teorem. Zanimljivosti i korisni savjeti

Godelov teorem o nepotpunosti

Uspenski V.A.

Možda je Gödelov teorem o nepotpunosti doista jedinstven. Jedinstvena po tome što se na nju pozivaju kada žele dokazati "sve na svijetu" - od prisutnosti bogova do odsutnosti razuma. Uvijek me zanimalo "primarnije pitanje" - a tko bi od onih koji se pozivaju na teorem o nepotpunosti mogao ne samo formulirati, nego i dokazati? Ovaj članak objavljujem iz razloga što predstavlja vrlo pristupačnu formulaciju Gödelovog teorema. Preporučujem da prvo pročitate članak Tullio Regge Kurt Gödel i njegov poznati teorem

Zaključak o nemogućnosti univerzalnog kriterija istine izravna je posljedica rezultata do kojeg je došao Tarski kombinirajući Gödelov teorem o neodlučivosti s vlastitom teorijom istine, prema kojoj ne može postojati univerzalni kriterij istine čak ni za relativno usko područje. teorije brojeva, a time i za svaku znanost koja koristi aritmetiku. Naravno, ovaj se rezultat a fortiori primjenjuje na koncept istine u bilo kojem nematematičkom području znanja u kojem se aritmetika široko koristi.

Karl Popper

Uspenski Vladimir Andrejevič rođen je 27. studenog 1930. u Moskvi. Diplomirao na Fakultetu mehanike i matematike Moskovskog državnog sveučilišta (1952.). Doktor fizikalno-matematičkih znanosti (1964). Profesor, predstojnik Katedre za matematičku logiku i teoriju algoritama Mehaničko-matematičkog fakulteta (1966). Održava kolegije predavanja "Uvod u matematičku logiku", "Izračunljive funkcije", "Gödelov teorem o potpunosti". Pripremio 25 kandidata i 2 doktora znanosti

1. Izjava problema

Teorem o nepotpunosti, čiju ćemo točnu formulaciju dati na kraju ovog poglavlja, a možda kasnije (ako čitatelja to zanima) i dokaz, tvrdi otprilike sljedeće: pod određenim uvjetima u bilo kojem jeziku postoje istiniti, ali nedokazive izjave.

Kada na ovaj način formuliramo teorem, gotovo svaka riječ zahtijeva neko objašnjenje. Stoga ćemo započeti s objašnjenjem značenja riječi koje koristimo u ovoj formulaciji.

1.1. Jezik

Nećemo dati najopćenitiju moguću definiciju jezika, radije ćemo se ograničiti na one jezične koncepte koji će nam kasnije trebati. Postoje dva takva pojma: "abeceda jezika" i "skup istinitih iskaza jezika".

1.1.1. Abeceda

Pod abecedom podrazumijevamo konačan skup elementarnih znakova (to jest stvari koje se ne mogu rastaviti na sastavne dijelove). Ti se znakovi nazivaju slovima abecede. Pod riječju abecede podrazumijevamo konačan niz slova. Na primjer, obične riječi u engleskom jeziku (uključujući vlastita imena) su riječi abecede od 54 slova (26 malih slova, 26 velikih slova, crtica i apostrof). Drugi primjer - prirodni brojevi u decimalnom zapisu su riječi abecede od 10 slova, čija su slova znakovi: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Za označavanje ćemo koristiti obična velika slova abecede. Ako je L abeceda, onda je L? označavat će skup svih riječi abecede L, - riječi sastavljene od njegovih slova. Pretpostavit ćemo da svaki jezik ima svoju abecedu, tako da su svi izrazi tog jezika (tj. imena raznih predmeta, izjave o tim objektima itd.) riječi ove abecede. Na primjer, svaka rečenica na engleskom jeziku, kao i svaki tekst napisan na engleskom, može se smatrati riječju proširene abecede od 54 slova, koja također uključuje interpunkcijske znakove, međuriječni razmak, crvenu crtu i eventualno neke drugi korisni znakovi. Pretpostavljajući da su jezični izrazi riječi neke abecede, stoga isključujemo iz razmatranja "višeslojne" izraze poput ???f(x)dx. Međutim, ovo ograničenje nije previše značajno, budući da se svaki takav izraz, korištenjem odgovarajućih konvencija, može "razvući" u linearni oblik. Svaki skup M sadržan u L? naziva se skup riječi abecede L. Ako jednostavno kažemo da je M skup riječi, tada mislimo da je to riječ neke abecede. Sada se gornja jezična pretpostavka može preformulirati na sljedeći način: u svakom jeziku, svaki skup izraza je skup riječi.

1.1.2. Puno istinitih tvrdnji

Pretpostavljamo da nam je dan podskup T skupa L? (gdje je L abeceda nekog jezika koji razmatramo), što se naziva skupom "istinitih izjava" (ili jednostavno "istina"). Prelazeći izravno na podskup T, izostavljamo sljedeće međukorake zaključivanja: prvo, koje su riječi abecede L dobro oblikovani izrazi jezika, to jest, imaju određeno značenje u našem tumačenju ovog jezika (na primjer , 2 + 3, x + 3, x=y, x=3, 2=3, 2=2 su dobro oblikovani izrazi, dok izrazi poput +=x nisu); drugo, koji su izrazi formule, tj. može ovisiti o parametru (npr. x=3, x=y, 2=3, 2=2); treće, koje su od formula zatvorene formule, tj. izjave koje ne ovise o parametrima (na primjer, 2=3, 2=2); i konačno, koje su zatvorene formule istinite tvrdnje (na primjer, 2=2).

1.1.3. Osnovni jezični par

1.2. "Nedokazivo"

"Nedokazivo" znači nemati dokaza.

1.3. Dokaz

Unatoč činjenici da je termin "dokaz" možda jedan od najvažnijih u matematici (Bourbaki svoju knjigu "Osnove matematike" počinju riječima: "Od vremena starih Grka, reći "matematika" značilo je isto što i govoreći "dokaz"), on nema preciznu definiciju. Općenito, pojam dokaza sa svim svojim semantičkim ograncima pripada prije području psihologije nego matematike. Ali kako god bilo, dokaz je jednostavno argument koji mi sami smatramo prilično uvjerljivim kako bismo uvjerili sve ostale.

Kada se zapiše, dokaz postaje riječ u nekoj abecedi P, baš kao što je svaki engleski tekst riječ u abecedi L, čiji je primjer dat gore. Skup svih dokaza čini podskup (i prilično velik podskup) skupa P?. Nećemo pokušavati dati preciznu definiciju ovog i "naivnog" i "apsolutnog" koncepta dokaza, ili - što je ekvivalentno - definirati odgovarajući podskup od P?. Umjesto toga, razmotrit ćemo formalnu analogiju ovog nejasnog koncepta, za koji ćemo i dalje koristiti izraz "dokaz" u onome što slijedi. Ovaj analog ima dvije vrlo važne značajke koje ga razlikuju od intuitivnog koncepta (iako intuitivna ideja dokaza još uvijek donekle odražava te značajke). Prije svega, pretpostavljamo da postoje različite koncepcije dokaza, to jest da su dopušteni različiti podskupovi dokaza u P?, čak i više od toga: mi ćemo, zapravo, pretpostaviti da se sama abeceda dokaza P može mijenjati . U nastavku ćemo zahtijevati da za svaku takvu koncepciju dokaza postoji učinkovita metoda, drugim riječima, algoritam koji bi nužno odredio je li data riječ abecede P dokaz ili nije. Također pretpostavljamo da postoji algoritam koji se uvijek može koristiti za određivanje koju tvrdnju dati dokaz dokazuje. (U mnogim situacijama, izjava koja se dokazuje je jednostavno zadnja izjava u nizu koraka koji čine dokaz.)

Stoga je naša konačna formulacija definicije sljedeća:

(1) Imamo abecedu L (abecedu jezika) i abecedu P (abecedu dokaza).

(2) Dan nam je skup P koji je podskup od P? i čiji se elementi nazivaju "dokazima". U nastavku ćemo pretpostaviti da imamo i algoritam koji nam omogućuje da odredimo je li proizvoljna riječ abecede P element skupa P, odnosno dokaz ili nije.

(3) Također imamo funkciju? (za pronalaženje onoga što je točno dokazano), čija je domena? zadovoljava uvjet P???P?, a čiji je raspon u P?. Pretpostavljamo da imamo algoritam koji izračunava ovu funkciju (točno značenje riječi "algoritam izračunava funkciju" je sljedeće: vrijednosti funkcije se dobivaju korištenjem ovog algoritma - skupa posebnih pravila transformacije). Reći ćemo da je element p? P je dokaz riječi?(p) abecede L.

Trojka<Р, Р, ?>, koji zadovoljava uvjete (1)-(3) naziva se deduktivni sustav nad abecedom L.

Za čitatelja koji je upoznat s uobičajenim načinom definiranja "dokaza" u terminima "aksioma" i "pravila zaključivanja", sada ćemo objasniti kako se ova metoda može smatrati posebnim slučajem definicije dane u odjeljku 1.3.2. To jest, dokaz se obično definira kao slijed takvih jezičnih izraza, od kojih je svaki ili aksiom ili prethodno dobiven iz već postojećih izjava korištenjem jednog od pravila zaključivanja. Ako abecedi našeg jezika dodamo novu riječ *, tada takav dokaz možemo napisati kao riječ sastavljenu pomoću dobivene abecede: niz izraza postaje riječ C1*C2*...*Cn. U ovom slučaju, funkcija koja određuje što je točno dokazano ima svoju vrijednost u dijelu ove riječi neposredno iza zadnjeg slova * u nizu. Algoritam čije se postojanje zahtijeva u odjeljku 1.3.2. definicije, mogu se lako konstruirati nakon što smo točno definirali bilo koje od prihvaćenih značenja riječi "aksiom" i "pravilo zaključivanja".

1.4. Pokušaji točne formulacije teorema o nepotpunosti

1.4.1. Prvi pokušaj

„Pod određenim uvjetima za temeljni par jezika abecede L i deduktivnog sustava<Р, Р, ?>iznad L, uvijek postoji riječ u T koja nema dokaz. Ova opcija još uvijek izgleda nejasno. Konkretno, lako bismo mogli smisliti koliko god želimo deduktivnih sustava, s vrlo malo dokazivih riječi. ?) nema riječi za sve to bi imali dokaze.

1.4.2. Drugi pokušaj

Postoji još jedan, prirodniji pristup. Pretpostavimo da nam je dan jezik - u smislu da nam je dan temeljni par tog jezika. Sada ćemo tražiti takav deduktivni sustav nad L (intuitivno, tražimo tehniku ​​dokazivanja) s kojim bismo mogli dokazati što više riječi iz T, u granicama svih riječi iz T. Gödelov teorem opisuje situaciju u kojoj takav deduktivni sustav (po kojem bi svaka riječ u T bila dokaziva) ne postoji. Stoga bismo željeli formulirati sljedeću izjavu:

"Pod određenim uvjetima u vezi s temeljnim parom, ne postoji takav deduktivni sustav u kojem bi svaka riječ iz T imala dokaz."

Međutim, takva je tvrdnja očito netočna, jer je potrebno samo uzeti deduktivni sustav u kojem je P = L, P = P? i?(p) = p za sve p u P?; onda svaka riječ od L? trivijalno je dokazivo. Stoga moramo prihvatiti neka ograničenja u pogledu toga koje deduktivne sustave koristimo.

1.5. Dosljednost

Bilo bi sasvim prirodno zahtijevati da se mogu dokazati samo "istiniti iskazi", to jest samo riječi iz T. Reći ćemo da deduktivni sustav<Р, Р, ?>je konzistentan u odnosu na temeljni par if?(P)?T. U svim daljnjim razmišljanjima zanimat će nas samo takvi konzistentni deduktivni sustavi. Ako nam je dan jezik, tada bi bilo krajnje primamljivo pronaći takav konzistentan deduktivni sustav u kojem bi svaka istinita izjava imala dokaz. Upravo varijanta Gödelovog teorema koja nas zanima kaže da je pod određenim uvjetima s obzirom na temeljni par nemoguće pronaći takav deduktivni sustav.

1.6. potpunost

Kaže se da deduktivni sustav<Р,Р,?>je potpun u odnosu na temeljni par, pod uvjetom da ?(P)?T. Tada naša formulacija teorema o nepotpunosti ima sljedeći oblik:

Pod određenim uvjetima u vezi s temeljnim parom, ne postoji takav deduktivni sustav<Р,Р,?>preko L koji bi bio i potpun i relativno dosljedan.

Bibliografija

Za izradu ovog rada korišteni su materijali sa stranice http://filosof.historic.ru.

Priznajem da sam samu ideju o razmatranju pitanja postojanja Boga s ove strane pročitao od Anatolija Aleksandroviča Wassermana:
http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%B0%D1%82%D0%BE%D0%BB%D0%B8%D0%B9_%D0%90%D0 %BB%D0%B5%D0%BA%D1%81%D0%B0%D0%BD%D0%B4%D1%80%D0%BE%D0%B2%D0%B8%D1%87_%D0%92 %D0%B0%D1%81%D1%81%D0%B5%D1%80%D0%BC%D0%B0%D0%BD#.D0.A0.D0.B5.D0.BB.D0.B8. D0.B3.D0.B8.D0.BE.D0.B7.D0.BD.D1.8B.D0.B5_.D0.B2.D0.B7.D0.B3.D0.BB.D1.8F.D0. B4.D1.8B

Ali želio bih razviti ovu ideju i opisati je malo detaljnije.
U vjeri (kao i ne u vjeri) postoji neka aksiomatska konstrukcija. Barem u idealnom slučaju, ako se ne radi samo o slijepom uvjerenju, već o svjesnom i informiranom izboru. Na primjer, aksiom fizike može se smatrati "priroda je spoznatljiva uz pomoć razuma i logičkog zaključivanja, svi zakoni fizike su isti u svim točkama prostora iu bilo koje vrijeme." Na primjer, izjava "Bog postoji i temeljni je uzrok svih stvari" može se smatrati aksiomom religije. Drugim riječima, nema sumnje da se sve brojne pojedinosti i grane mogu svesti na nekoliko najvažnijih tvrdnji koje se nikako ne mogu dokazati, a to su sami aksiomi.

Razmotrite religijska uvjerenja s ovih pozicija. Najvažniji aksiom religije: "Bog postoji i temeljni je uzrok svih stvari."
Sada se prisjetimo jednog od najvažnijih matematičkih teorema, Gödelovog teorema.
http://elementy.ru/trefil/21142
Gödelov slabi teorem: "Svaki formalni sustav aksioma sadrži nerazriješene pretpostavke" ili "ako je sustav aksioma potpun, onda je nekonzistentan."
Gödelov jaki teorem: "Logička potpunost (ili nepotpunost) bilo kojeg sustava aksioma ne može se dokazati unutar okvira ovog sustava. Dodatni aksiomi (koji pojačavaju sustav) su potrebni da se to dokaže ili opovrgne."

Podsjetimo se na neke definicije. Sustav aksioma je potpun ako je bilo koja tvrdnja formulirana za dati sustav aksioma dokaziva (to jest, istinita je ili netočna). Nerazriješena pretpostavka je izjava za koju se ne može dokazati ni istinitost ni netočnost, odnosno izjava nije logički dokaziva. Sustav aksioma je nedosljedan ako se, s obzirom na istu tvrdnju, može dokazati i njezina istinitost i lažnost.

Iz Godelovog teorema proizlazi da ako je pojam Boga uključen u aksiomatski sustav, tada taj sustav nije potpun, odnosno postoje posljedice (fenomeni) koji nisu dokazivi, odnosno mogu, ali i ne moraju postojati, to nije dokazivo.
Ali to je u suprotnosti sa sljedeća dva prijedloga (odaberite onaj koji je najuvjerljiviji): priroda ne sadrži fenomene koji se mogu smatrati i postojećim i nepostojećim, svaki prirodni fenomen ili postoji ili ne postoji. Druga odredba kaže da je, po definiciji, Bog temeljni uzrok svega, stoga Bog ili dovodi do postojanja nekih stvari (izjava) ili do njihovog nepostojanja, pozivajući se na Boga, možete ili dokazati ili opovrgnuti bilo koju izjavu. To je u suprotnosti s nedovršenošću sustava.

Ili drugačije. Ako uključimo pojam Boga u aksiomatski sustav i pretpostavimo da je potpun (svaka tvrdnja u potpunom skupu aksioma je dokaziva), tada će prema Gödelovom teoremu takav sustav aksioma biti nedosljedan, odnosno postojat će pojave za koje se može dokazati da i postoje i ne postoje.

Boga nema smisla uključivati ​​u proturječni sustav aksioma, budući da je on proturječan, odnosno sadrži pojave za koje se može dokazati da i postoje i ne postoje, što je, kako je rečeno, proturječno prirodi i koncept Boga.

Konačno, ako pojam Boga nije uključen u aksiomatski sustav, onda se on ne može smatrati temeljnom osnovom svemira, iz koje proizlazi sve što postoji, što je u biti kontradiktorno definiciji Boga.

Za valjanost ovog dokaza potrebno je priznati valjanost zakona matematičke logike (logika iskaza + račun predikata), koji omogućuju utvrđivanje zakona posljedice, istine, lažnosti, nedosljednosti, konzistentnosti iskaza i dr. svojstva i odnosi između iskaza.

Ako pak pretpostavimo da matematička logika nije primjenjiva na proučavanje pitanja o postojanju Boga, tada posljedica neće biti mogućnost proučavanja ovog pitanja uz pomoć zaključivanja, uz pomoć razuma. Drugim riječima, dosljedan razum uvijek dolazi do niječnog odgovora na pitanje postojanja Boga.

Što se događa kao rezultat ... svaka barem donekle racionalna osoba, naravno, priznaje valjanost zakona logike, što znači da uvijek dolazi do zaključka da Bog u definiciji "uzroka svih stvari" čini ne postoji. Neracionalna osoba koja tvrdi da se Boga može spoznati samo uz pomoć osjećaja (a ne razuma), naravno, može to reći, ali nema načina da se u to uvjeri drugoga, osjećaji se ne mogu prenijeti. Štoviše, pojam Boga je pojam formuliran razumom. Kako se predlaže prevesti koncept razuma u osjet, pa čak i tako da se može prenijeti na drugu osobu, nije jasno. Opet, barem iole racionalan čovjek reći će da to nije moguće: apstraktni pojam razuma prevesti u osjećaj i osjetiti ga.

Na kraju, postoji još jedna opcija: "Bog nije temeljni uzrok svega." Tada takve proturječnosti ne nastaju, ali to je značajno slabljenje pozicije religije, jer je upravo činjenica da je Bog sve stvorio, da je Bog početak svih početaka, temelj za brojne religijske iskaze i opravdanja u sporovi.

p.s. Vrijedno je primijetiti još jednu zanimljivu stvar, već zanimljivu za fizičare. Ova definicija Boga ne govori ništa o njegovoj racionalnosti. Odnosno, moglo bi se dodati "Bog je razumni uzrok svih stvari", ali to je sužavanje definicije, koja u početku nije potrebna za dokaz. Bez inteligencije, koncept "boga" može se lako zamijeniti "singularnošću i velikim praskom - uzrokom svih stvari". A odgovor će biti isti: singularnost i veliki prasak nisu glavni uzrok svega.
Nakon još veće apstrakcije, možemo reći da niti jedna pojava ili razlog ne može biti temeljni uzrok svega postojećeg, odnosno temeljni uzrok u principu ne postoji. Argumentirajući u okviru bilo koje aksiomatike, može se doći do zaključka da temeljni uzrok svega ne postoji. Jednostavno rečeno, bez obzira koliko duboko poznajemo svemir, uvijek će biti pitanja poput: "odakle veliki prasak, odakle singularnost, odakle pulsirajući svemir, odakle je multiverzum odakle dolazi, zašto svemir uvijek postoji?" itd. Uzrok svega se u principu ne može pronaći, on nije sadržan ni u jednom predmetu, pojavi ili pojmu. Stoga je za osobu to jednako njegovoj odsutnosti. Teoretski, moguće je pretpostaviti postojanje vanjskog promatrača izvan našeg svemira, što će dati odgovor na pitanje odakle je sve došlo (isti dodatni aksiom, proširenje u Gödelovom teoremu), ali onda se postavlja pitanje odakle je li došao vanjski promatrač, njegov svemir i temeljni uzrok svega ovoga.

Svaki sustav matematičkih aksioma, počevši od određene razine složenosti, interno je nekonzistentan ili nepotpun.

Godine 1900. u Parizu je održana Svjetska konferencija matematičara na kojoj je David Hilbert (1862.-1943.) u obliku sažetaka predstavio 23 najvažnija, po njegovom mišljenju, problema koje je on formulirao, a koje su trebali riješiti teoretski znanstvenici. nadolazećeg dvadesetog stoljeća. Broj dva na njegovom popisu bio je jedan od onih jednostavnih problema koji se čine očitima dok ne zakopate malo dublje. U modernom smislu, to je bilo pitanje: je li matematika sama po sebi dovoljna? Hilbertov drugi problem bio je rigorozno dokazati da sustav aksiomi- osnovne tvrdnje koje se u matematici uzimaju kao osnova bez dokaza - savršena je i potpuna, odnosno omogućuje vam da matematički opišete sve što postoji. Trebalo je dokazati da je moguće postaviti takav sustav aksioma da će, prvo, biti međusobno konzistentni, a drugo, iz njih se može izvesti zaključak o istinitosti ili lažnosti bilo koje tvrdnje.

Uzmimo primjer iz školske geometrije. Standard Euklidska planimetrija(geometrija na ravnini) moguće je bezuvjetno dokazati da je tvrdnja "zbroj kutova trokuta 180°" točna, a tvrdnja "zbroj kutova trokuta 137°" netočna. U suštini govoreći, u euklidskoj geometriji svaka izjava je ili lažna ili istinita, a treća nije dana. A početkom dvadesetog stoljeća matematičari su naivno vjerovali da bi se ista situacija trebala promatrati u svakom logički dosljednom sustavu.

A onda je 1931. neki bečki matematičar s naočalama Kurt Godel uzeo i objavio kratki članak koji je naprosto prevrnuo cijeli svijet takozvane "matematičke logike". Nakon dugih i složenih matematičkih i teorijskih preambula, doslovno je utvrdio sljedeće. Uzmimo bilo koju izjavu poput: "Pretpostavka #247 je logički nedokaziva u ovom sustavu aksioma" i nazovimo je "izjava A". Tako je Gödel jednostavno dokazao sljedeće nevjerojatno svojstvo bilo koji sustavi aksioma:

"Ako se izjava A može dokazati, onda se može dokazati izjava koja nije A."

Drugim riječima, ako je moguće dokazati valjanost tvrdnje „Pretpostavka 247 ne dokazivo", tada je moguće dokazati valjanost tvrdnje "Pretpostavka 247 dokazivo". To jest, vraćajući se na formulaciju drugog Hilbertovog problema, ako je sustav aksioma potpun (to jest, bilo koja tvrdnja u njemu se može dokazati), onda je nedosljedan.

Jedini izlaz iz ove situacije je prihvaćanje nepotpunog sustava aksioma. To jest, moramo se pomiriti s činjenicom da ćemo u kontekstu bilo kojeg logičkog sustava ostati s izjavama tipa A koje su očito istinite ili lažne - a njihovu istinitost možemo prosuditi samo vani okvir aksiomatike koji smo usvojili. Ako takvih tvrdnji nema, onda je naša aksiomatika kontradiktorna, a unutar njezina okvira neizbježno će postojati formulacije koje je moguće i dokazati i opovrgnuti.

Dakle, formulacija prvi,ili slab Gödelovi teoremi o nepotpunosti: "Svaki formalni sustav aksioma sadrži nerazriješene pretpostavke." Ali Gödel nije tu stao, formulirajući i dokazujući drugi, ili snažna Godelov teorem o nepotpunosti: “Logička potpunost (ili nepotpunost) bilo kojeg sustava aksioma ne može se dokazati unutar okvira ovog sustava. Da bi se to dokazalo ili opovrglo, potrebni su dodatni aksiomi (jačanje sustava).“

Bilo bi sigurnije misliti da su Godelovi teoremi apstraktni i da se ne tiču ​​nas, već samo područja uzvišene matematičke logike, no zapravo se pokazalo da su oni izravno povezani sa strukturom ljudskog mozga. Engleski matematičar i fizičar Roger Penrose (rođen 1931.) pokazao je da se Gödelovi teoremi mogu koristiti za dokazivanje temeljnih razlika između ljudskog mozga i računala. Poanta njegova razmišljanja je jednostavna. Računalo djeluje strogo logično i nije u stanju utvrditi je li izjava A istinita ili netočna ako izlazi iz okvira aksiomatike, a takve izjave, prema Gödelovom teoremu, neizbježno postoje. Osoba, suočena s takvom logički nedokazivom i nepobitnom tvrdnjom A, uvijek je u mogućnosti utvrditi njezinu istinitost ili netočnost – na temelju svakodnevnog iskustva. Barem u ovome, ljudski je mozak superiorniji od računala okovanog čistim logičkim sklopovima. Ljudski mozak je u stanju razumjeti svu dubinu istine sadržanu u Gödelovim teoremima, ali kompjuterski to ne može nikada. Stoga je ljudski mozak sve samo ne računalo. Sposoban je donositi odluke, i Turingov test će proći.

Pitam se je li Hilbert uopće znao koliko će nas njegova pitanja odvesti daleko?

Kurt Godel, 1906.-78

Austrijski, potom američki matematičar. Rođen u Brünnu (Brünn, sada Brno, Češka). Diplomirao je na Sveučilištu u Beču, gdje je ostao nastavnik na Odsjeku za matematiku (od 1930. - profesor). Godine 1931. objavio je teorem koji je kasnije dobio njegovo ime. Budući da je bio čisto apolitična osoba, izuzetno je teško preživio ubojstvo svog prijatelja i zaposlenika odjela od strane nacističkog studenta i pao u duboku depresiju čiji su ga recidivi pratili do kraja života. Tridesetih godina prošlog stoljeća emigrirao je u SAD, ali se vratio u rodnu Austriju i oženio. Godine 1940., u jeku rata, bio je prisiljen pobjeći u Ameriku u tranzitu kroz SSSR i Japan. Neko je vrijeme radio na Institutu za napredne studije Princeton. Nažalost, psiha znanstvenika to nije mogla podnijeti, te je umro od gladi u psihijatrijskoj klinici, odbijajući jesti, jer je bio uvjeren da ga namjeravaju otrovati.

Jedan od najpoznatijih teorema matematičke logike, sretan i nesretan u isto vrijeme. U tome je slična Einsteinovoj posebnoj teoriji relativnosti. S jedne strane, gotovo svi su čuli nešto o njima. S druge strane, u popularnom tumačenju, Einsteinova teorija, kao što znate, "kaže da je sve na svijetu relativno". I Gödelov teorem o nepotpunosti (u daljnjem tekstu jednostavno TGN), u približno jednako slobodnoj narodnoj formulaciji, "dokazuje da postoje stvari neshvatljive ljudskom umu". I tako ga neki pokušavaju prilagoditi kao argument protiv materijalizma, dok drugi, naprotiv, uz njegovu pomoć dokazuju da Boga nema. Smiješno je ne samo to što obje strane ne mogu biti u pravu u isto vrijeme, nego i to što se ni jedna ni druga ne trude dokučiti što, zapravo, ovaj teorem kaže.

Pa što? U nastavku ću pokušati "na prstima" govoriti o tome. Moje izlaganje, naravno, neće biti strogo i intuitivno, ali ću zamoliti matematičare da me ne osuđuju strogo. Moguće je da će za nematematičare (u koje, zapravo, i ja spadam) biti nešto novo i korisno u ovome u nastavku.

Matematička logika je doista prilično komplicirana znanost, i što je najvažnije, nije baš poznata. Zahtijeva pažljive i stroge manevre, u kojima je važno ne brkati stvarno dokazano s činjenicom da je "već jasno". Međutim, nadam se da će čitatelju za razumijevanje sljedećeg “skica dokaza TGN-a” trebati samo znanje školske matematike/informatike, vještine logičkog razmišljanja i 15-20 minuta vremena.

Nešto pojednostavljujući, TGN tvrdi da u dovoljno složenim jezicima postoje nedokazivi prijedlozi. Ali u ovoj frazi gotovo svaka riječ treba objašnjenje.

Počnimo pokušavajući shvatiti što je dokaz. Uzmimo neki školski zadatak iz aritmetike. Na primjer, neka je potrebno dokazati točnost sljedeće nekomplicirane formule: "" (podsjećam vas da se simbol čita "za bilo koji" i naziva se "univerzalni kvantifikator"). Može se dokazati identičnom transformacijom, recimo ovako:

Prijelaz s jedne formule na drugu događa se prema određenim dobro poznatim pravilima. Prijelaz s 4. formule na 5. dogodio se, recimo, zato što je svaki broj jednak sam sebi - takav je aksiom aritmetike. I cijeli postupak dokazivanja, dakle, prevodi formulu u booleovu vrijednost TRUE. Rezultat bi mogao biti NETOČAN - ako bismo pobili neku formulu. U ovom slučaju bismo dokazali njegovu negaciju. Moguće je zamisliti program (i takvi su programi zapravo napisani) koji bi dokazao takve (i složenije) tvrdnje bez ljudske intervencije.

Recimo istu stvar malo formalnije. Pretpostavimo da imamo skup koji se sastoji od nizova znakova neke abecede i postoje pravila po kojima se podskup tzv. izjave- odnosno gramatički smislene fraze, od kojih je svaka istinita ili lažna. Možemo reći da postoji funkcija koja spaja izjave s jednom od dvije vrijednosti: TRUE ili FALSE (to jest, preslikava ih u Booleov skup od dva elementa).

Nazovimo takav par - skup izjava i funkcija od do - "jezik iskaza". Imajte na umu da je u svakodnevnom smislu pojam jezika nešto širi. Na primjer, ruski izraz — Pa dođi ovamo! nije istinita i nije lažna, odnosno, sa stajališta matematičke logike, nije izjava.

Za ono što slijedi potreban nam je pojam algoritma. Ovdje neću davati njegovu formalnu definiciju - to bi nas odvelo prilično u stranu. Ograničit ću se na neformalno: "algoritam"- ovaj niz nedvosmislenih uputa ("program"), koji u konačnom broju koraka pretvara ulazne podatke u izlazne. Kurziv je fundamentalno važan - ako se program zaglavi na nekim početnim podacima, onda ne opisuje algoritam. Radi jednostavnosti i primjene na naš slučaj, čitatelj može smatrati da je algoritam program napisan u bilo kojem njemu poznatom programskom jeziku, za koji je zajamčeno da će dovršiti svoj rad s Booleovim rezultatom za bilo koji ulazni podatak iz dane klase.

Zapitajmo se: postoji li "algoritam dokazivanja" za svaku funkciju (ili, ukratko, "deduktivno") ekvivalentno ovoj funkciji, to jest, prevođenje svake izjave u točno istu booleovu vrijednost kao ona? Konciznije, isto se pitanje može formulirati na sljedeći način: je li svaka funkcija nad skupom iskaza izračunljiv? Kao što već možete pretpostaviti, iz valjanosti TGN-a proizlazi da ne, ne bilo koje - postoje neizračunljive funkcije ovog tipa. Drugim riječima, ne može se dokazati svaka istinita izjava.

Vrlo je moguće da će ova izjava kod vas izazvati unutarnji protest. To je zbog nekoliko okolnosti. Prvo, kada nas uče matematiku u školi, ponekad postoji pogrešan dojam da su fraze “teorem je istinit” i “moguće je dokazati ili potvrditi teorem” gotovo identične. Ali ako razmislite o tome, to uopće nije očito. Neki se teoremi dokazuju vrlo jednostavno (npr. nabrajanjem malog broja opcija), a neki su vrlo teški. Razmotrimo, na primjer, Fermatov slavni posljednji teorem:

dokaz za koji je pronađen tek tri i pol stoljeća nakon prve formulacije (i daleko je od elementarnog). Potrebno je razlikovati istinitost iskaza od njegove dokazivosti. Ni iz čega ne proizlazi da ne postoje istinite, nego nedokazive (i ne do kraja provjerljive) tvrdnje.

Drugi intuitivni argument protiv TGN-a je suptilniji. Pretpostavimo da imamo neki nedokaziv (u okviru ovog deduktivnog) iskaz. Što nas sprječava da to prihvatimo kao novi aksiom? Dakle, malo ćemo komplicirati naš sustav dokaza, ali to nije strašno. Ovaj bi argument bio savršeno točan kada bi postojao konačan broj nedokazivih tvrdnji. U praksi se može dogoditi sljedeće - nakon postuliranja novog aksioma, naići ćete na novu nedokazivu tvrdnju. Uzmite to kao još jedan aksiom - naletjet ćete na treći. I tako u nedogled. Kažu deductica će ostati nepotpun. Također možemo poduzeti snažne mjere tako da algoritam za dokazivanje završi nakon konačnog broja koraka s nekim rezultatom za bilo koju izjavu jezika. Ali u isto vrijeme će početi lagati - navoditi na istinu za netočne izjave, ili na laži - za vjernike. U takvim se slučajevima kaže da deduktivna kontradiktoran. Dakle, još jedna formulacija TGN-a zvuči ovako: "Postoje propozicioni jezici za koje je potpuna dosljedna dedukcija nemoguća" - otuda i naziv teorema.

Ponekad se naziva "Gödelovim teoremom" tvrdnja da svaka teorija sadrži probleme koji se ne mogu riješiti unutar okvira same teorije i zahtijevaju njezinu generalizaciju. U izvjesnom smislu to je istina, iako takva formulacija zamagljuje problem umjesto da ga pojašnjava.

Također napominjem da ako govorimo o uobičajenim funkcijama koje preslikavaju skup realnih brojeva u njega, tada "neizračunljivost" funkcije nikoga ne bi iznenadila (samo nemojte brkati "izračunljive funkcije" i "izračunljive brojeve" - to su različite stvari). Svaki školarac zna da, recimo, u slučaju funkcije morate imati puno sreće s argumentom kako bi proces izračunavanja točnog decimalnog prikaza vrijednosti te funkcije završio u konačnom broju koraka. I najvjerojatnije ćete ga izračunati pomoću beskonačnog niza, a ovaj izračun nikada neće dovesti do točnog rezultata, iako mu se može približiti - jednostavno zato što je vrijednost sinusa većine argumenata iracionalna. TGN nam jednostavno govori da čak i među funkcijama čiji su argumenti stringovi i čije su vrijednosti nula ili jedan, neizračunljive funkcije, iako raspoređene na potpuno drugačiji način, također postoje.

Za ono što slijedi opisat ćemo "jezik formalne aritmetike". Razmotrimo klasu tekstualnih nizova konačne duljine koji se sastoje od arapskih brojeva, varijabli (slova latinične abecede) koje imaju prirodne vrijednosti, razmaka, znakova aritmetičkih operacija, jednakosti i nejednakosti, kvantifikatora ("postoji") i ("za" bilo koji”) i, možda, , neki drugi simboli (njihov točan broj i sastav za nas su nevažni). Jasno je da nisu svi takvi redovi smisleni (na primjer, "" je besmislica). Podskup smislenih izraza iz ove klase (to jest, nizovi koji su istiniti ili lažni u smislu obične aritmetike) bit će naš skup iskaza.

Primjeri formalnih aritmetičkih izjava:

itd. Nazovimo sada "formulu sa slobodnim parametrom" (FSP) niz koji postaje iskaz ako se prirodni broj zamijeni u njega kao ovaj parametar. Primjeri FSP-a (s parametrom):

itd. Drugim riječima, FSP-ovi su ekvivalentni funkcijama prirodnog argumenta s Booleovom vrijednošću.

Skup svih FSP-ova označimo slovom . Jasno je da se može naručivati ​​(npr. prvo ispisujemo jednoslovne formule poredane abecednim redom, zatim dvoslovne itd.; nije nam bitno kojom će se abecedom odvijati poredak). Dakle, bilo koji FSP odgovara svom broju na uređenom popisu, a mi ćemo ga označiti .

Okrenimo se sada skici dokaza TGN u sljedećoj formulaciji:

• Za iskazni jezik formalne aritmetike ne postoji potpuna dosljedna dedukcija.

Dokazat ćemo kontradikcijom.

Dakle, pretpostavimo da takav deduktiv postoji. Opišimo sljedeći pomoćni algoritam koji prirodnom broju dodjeljuje booleovu vrijednost na sljedeći način:

Jednostavno rečeno, algoritam daje vrijednost TRUE ako i samo ako rezultat zamjene u FSP vlastitog broja na našem popisu daje lažnu izjavu.

Ovdje dolazimo do jedinog mjesta gdje ću zamoliti čitatelja da mi vjeruje na riječ.

Očito, pod gornjom pretpostavkom, bilo koji FSP iz može se pridružiti algoritmu koji sadrži prirodni broj na ulazu i Booleovu vrijednost na izlazu. Manje očito je suprotno:

Dokaz ove leme zahtijevao bi barem formalnu, a ne intuitivnu definiciju pojma algoritma. Međutim, ako malo razmislite o tome, sasvim je vjerojatno. Doista, algoritmi su napisani u algoritamskim jezicima, među kojima ima i takvih egzotičnih kao što je, na primjer, Brainfuck, koji se sastoji od osam riječi od jednog znaka, u kojima se, međutim, može implementirati bilo koji algoritam. Bilo bi čudno da se bogatiji jezik formalnih aritmetičkih formula koji smo opisali pokaže siromašnijim - iako, bez sumnje, nije baš prikladan za obično programiranje.

Prošavši ovo sklisko mjesto, brzo dolazimo do kraja.

Dakle, gore smo opisali algoritam. Prema lemi u koju sam tražio da vjerujete, postoji ekvivalentan FSP. Ima neki broj na popisu - recimo . Zapitajmo se, koja je svrha? Neka bude ISTINA. Tada, prema konstrukciji algoritma (a time i njemu ekvivalentne funkcije), to znači da je rezultat zamjene broja u funkciju LAŽ. Suprotno se provjerava na isti način: iz FALSE slijedi TRUE. Došli smo do kontradikcije, što znači da je izvorna pretpostavka pogrešna. Dakle, za formalnu aritmetiku ne postoji potpuna dosljedna dedukcija. Q.E.D.

Ovdje je prikladno prisjetiti se Epimenida (vidi portret u naslovu), koji je, kao što znate, izjavio da su svi Krećani lažljivci, budući da je i sam bio Krećanin. U sažetijoj formulaciji, njegova izjava (poznata kao "paradoks lažljivca") može se formulirati kao: "Lažem." Upravo takvu tvrdnju, koja sama proglašava svoju netočnost, upotrijebili smo za dokaz.

Zaključno, želim napomenuti da TGN ne tvrdi ništa posebno iznenađujuće. Uostalom, svi su odavno navikli na činjenicu da se svi brojevi ne mogu prikazati kao omjer dva cijela broja (sjećate se, ova izjava ima vrlo elegantan dokaz koji je star više od dvije tisuće godina?). A korijeni polinoma s racionalnim koeficijentima također nisu svi brojevi. A sada se pokazalo da nisu sve funkcije prirodnog argumenta izračunljive.

Skica danog dokaza bila je za formalnu aritmetiku, ali nije teško vidjeti da se THN odnosi i na mnoge druge iskazne jezike. Naravno, nisu svi jezici takvi. Na primjer, definirajmo jezik ovako:

• "Svaka fraza na kineskom jeziku je istinita izjava ako je sadržana u citatniku druga Mao Tse Tunga, a netočna je ako nije sadržana."

Tada odgovarajući potpuni i dosljedni algoritam dokazivanja (može se nazvati "dogmatski deduktivni") izgleda otprilike ovako:

• “Prelistajte knjigu citata druga Mao Tse Tunga dok ne pronađete izjavu koju tražite. Ako je pronađena, onda je istinita, a ako je citatnik gotov, a izjava nije pronađena, onda je lažna.

Tu nas spašava činjenica da je svaki citat očito konačan, pa će proces "dokazivanja" neminovno završiti. Stoga je TGN neprimjenjiv na jezik dogmatskih izjava. Ali govorili smo o složenim jezicima, zar ne?

na temu: "GODELOV TEOREM"

Kurt Gödel

Kurt Gödel - najveći stručnjak za matematičku logiku - rođen je 28. travnja 1906. u Brunnu (danas Brno, Češka). Diplomirao je na Sveučilištu u Beču, gdje je obranio doktorsku disertaciju, bio docent 1933–1938. Nakon anšlusa emigrirao je u SAD. Od 1940. do 1963. Gödel je radio na Institutu za napredne studije Princeton. Gödel je počasni doktorat sa sveučilišta Yale i Harvard, član Nacionalne akademije znanosti SAD-a i Američkog filozofskog društva.

Godine 1951. Kurt Gödel dobio je najveću znanstvenu nagradu u Sjedinjenim Državama, Einsteinovu nagradu. U članku posvećenom ovom događaju, još jedan od najvećih matematičara našeg vremena, John von Neumann, napisao je: “Doprinos Kurta Gödela modernoj logici je uistinu monumentalan. Ovo je više od samog spomenika. Ovo je prekretnica koja razdvaja dva razdoblja... Bez imalo pretjerivanja može se reći da je Gödelov rad iz temelja promijenio sam predmet logike kao znanosti.

Doista, čak i suhoparni popis Godelovih postignuća u matematičkoj logici pokazuje da je njihov autor u biti postavio temelje cijelim dijelovima ove znanosti: teoriji modela (1930; tzv. teorem o potpunosti uskog predikatskog računa, pokazujući, grubo govoreći, dostatnost sredstava "formalne logike ”za dokazivanje svih istinitih rečenica izraženih u njezinu jeziku), konstruktivne logike (1932–1933; rezultati o mogućnosti redukcije nekih klasa rečenica klasične logike na njihove intuicionističke dvojnike, koji postavio je temelje za sustavnu upotrebu “operacija uranjanja” koje omogućuju takvu redukciju različitih logičkih sustava jednih na druge), formalne aritmetike (1932. – 1933.; rezultati o mogućnosti redukcije klasične aritmetike na intuicionističku aritmetiku, pokazujući u određenom smislu dosljednost prve u odnosu na drugu), teorija algoritama i rekurzivnih funkcija (1934; definicija pojma opće rekurzivne funkcije, koja je odigrala odlučujuću ulogu u utvrđivanju algoritamske nerješivosti niza važnih problema u matematici, s jedne strane. I u implementaciji logičkih i matematičkih problema na elektroničkim računalima – s druge strane), aksiomatska teorija skupova (1938.; dokaz relativne konzistentnosti aksioma izbora i Cantorove hipoteze o kontinuumu iz aksioma teorije skupova, koja je označila početak niza važnih rezultata o relativnoj dosljednosti i neovisnosti teoretskih načela skupova).

Godelov teorem o nepotpunosti

Uvod

Godine 1931. u jednom od njemačkih znanstvenih časopisa pojavio se relativno mali članak prilično zastrašujućeg naslova "O formalno neodlučivim propozicijama Principia Mathematica i srodnih sustava". Njegov autor bio je dvadesetpetogodišnji matematičar sa Sveučilišta u Beču, Kurt Gödel, koji je kasnije radio na Institutu za napredne studije Princeton. Ovo je djelo imalo odlučujuću ulogu u povijesti logike i matematike. U odluci Sveučilišta Harvard da Gödelu dodijeli počasni doktorat (1952.) okarakterizirana je kao jedno od najvećih dostignuća moderne logike.

Međutim, u vrijeme izdavanja nije bilo naslova Gödelova djela. Ni njegov sadržaj većini matematičara nije ništa rekao. Spomenuta u naslovu, Principia Mathematica je monumentalna rasprava Alfreda North Whiteheada i Bertranda Russella u tri sveska o matematičkoj logici i temeljima matematike; poznavanje rasprave nipošto nije bilo nužan uvjet za uspješan rad u većini grana matematike. Zanimanje za pitanja kojima se bavio Gödelov rad uvijek je pripadala vrlo maloj skupini znanstvenika. U isto vrijeme, argumenti koje je Gödel dao u svojim dokazima bili su toliko neobični za svoje vrijeme. Da je njihovo potpuno razumijevanje zahtijevalo isključivo poznavanje predmeta i poznavanje literature posvećene tim vrlo specifičnim problemima.

Prvi teorem o nepotpunosti

Gödelov prvi teorem o nepotpunostičini se najznačajnijim rezultatom u matematičkoj logici. Zvuči ovako:

Za proizvoljnu dosljednu formalnu i izračunljivu teoriju u kojoj se mogu dokazati osnovni aritmetički iskazi, može se konstruirati pravi aritmetički iskaz čija se istinitost ne može dokazati unutar okvira teorije. Drugim riječima, svaka savršeno korisna teorija koja je dovoljna da predstavi aritmetiku ne može biti i dosljedna i potpuna.

Ovdje riječ "teorija" znači "beskonačan skup" tvrdnji, od kojih se za neke pretpostavlja da su istinite bez dokaza (takve tvrdnje nazivaju se aksiomi), dok se druge (teoremi) mogu izvesti iz aksioma, pa se stoga pretpostavljaju ( dokazano) biti istinit. Izraz "dokaziv u teoriji" znači "deduciran iz aksioma i primitiva teorije (konstantnih simbola abecede) korištenjem standardne logike (prvog reda)." Teorija je dosljedna (dosljedna) ako je u njoj nemoguće dokazati proturječnu tvrdnju. Izraz "može se izgraditi" znači da postoji neki mehanički postupak (algoritam) koji može izgraditi izjavu temeljenu na aksiomima, primitivima i logici prvog reda. "Elementarna aritmetika" je prisutnost operacija zbrajanja i množenja nad prirodnim brojevima. Rezultirajuća istinita, ali nedokaziva tvrdnja često se za danu teoriju naziva "Gödelovim nizom", ali postoji beskonačan broj drugih tvrdnji u teoriji koje imaju isto svojstvo nedokazivosti unutar teorije.

Pretpostavka da je teorija izračunljiva znači da je u načelu moguće implementirati računalni algoritam (računalni program) koji će (ako mu se dopusti izračunavanje proizvoljno dugih vremena, do beskonačnosti) izračunati popis svih teorema teorije. Zapravo, dovoljno je izračunati samo popis aksioma i svi se teoremi mogu učinkovito izvesti iz takvog popisa.

Prvi teorem o nepotpunosti nazvan je "Teorem VI" u Gödelovom radu iz 1931. O formalno neodlučivim propozicijama u Principia Mathematica i srodnim sustavima I. U Gödelovoj izvornoj snimci to je zvučalo ovako:

“Opći zaključak o postojanju neodlučivih propozicija je sljedeći:

Teorem VI .

Za svaku ω-konzistentnu rekurzivnu klasu k FORMULA postoje rekurzivni ZNAKOVI r takav da niti (v Gen r), niti ¬( v Gen r)ne pripadaju Flg (k)(gdje je v SLOBODNA VARIJABLA r ) ».

Oznaka Flg dolazi od njega. Folgerungsmenge- skup sekvenci, Gen dolazi od njega. generalizacija- generalizacija.

Grubo rečeno, Gödelova izjava G tvrdi: "istina G ne može se dokazati." Ako G mogla dokazati unutar okvira teorije, tada bi teorija sadržavala teorem koji je sam sebi proturječan, i stoga bi teorija bila nekonzistentna. Ali ako G nedokaziva, onda je istinita, pa je stoga teorija nepotpuna (izjava G nije izvodljivo u njemu).

Ovo objašnjenje je na običnom prirodnom jeziku i stoga nije baš matematički strogo. Kako bi pružio rigorozan dokaz, Gödel je numerirao izjave prirodnim brojevima. U ovom slučaju, teorija koja opisuje brojeve također pripada skupu propozicija. Pitanja o dokazivosti iskaza mogu se u ovom slučaju predstaviti kao pitanja o svojstvima prirodnih brojeva, koji moraju biti izračunljivi ako je teorija potpuna. U ovim terminima, Gödelova izjava kaže da ne postoji broj s nekim određenim svojstvom. Broj s ovim svojstvom bit će dokaz nekonzistentnosti teorije. Ako takav broj postoji, teorija je nedosljedna, suprotna izvornoj pretpostavci. Dakle, pod pretpostavkom da je teorija dosljedna (kao što sugerira premisa teorema), ispada da ne postoji takav broj, a Gödelova izjava je istinita, ali to se ne može dokazati unutar okvira teorije (stoga je teorija nepotpuna ). Važna konceptualna napomena je da se mora pretpostaviti da je teorija dosljedna kako bi se Gödelova izjava proglasila istinitom.

Drugi Gödelov teorem o nepotpunosti

Drugi Gödelov teorem o nepotpunosti glasi kako slijedi:

Za bilo koju formalno rekurzivno prebrojivu (tj. učinkovito generiranu) teoriju T, uključujući osnovne aritmetičke izjave o istinitosti i određene formalne izjave o dokazivosti, data teorija T uključuje izjavu o svojoj dosljednosti ako i samo ako je teorija T nekonzistentna.

Drugim riječima, konzistentnost dovoljno bogate teorije ne može se dokazati pomoću ove teorije. Međutim, moglo bi se pokazati da se dosljednost jedne određene teorije može uspostaviti pomoću druge, snažnije formalne teorije. Ali onda se postavlja pitanje dosljednosti ove druge teorije, i tako dalje.

Mnogi su pokušali upotrijebiti ovaj teorem kako bi dokazali da se inteligentna aktivnost ne može svesti na izračune. Primjerice, davne 1961. godine poznati logičar John Lucas osmislio je sličan program. Njegovo razmišljanje pokazalo se prilično ranjivim - međutim, on je zadatak postavio šire. Roger Penrose ima malo drugačiji pristup, koji je u knjizi prikazan potpuno, "od nule".

Rasprave

Posljedice teorema utječu na filozofiju matematike, posebno na one formalizme koji koriste formalnu logiku za definiranje svojih principa. Prvi teorem o nepotpunosti može se preformulirati na sljedeći način: nemoguće je pronaći opsežan sustav aksioma koji bi bio u stanju dokazati svi matematičke istine, a ne jednu laž". S druge strane, sa stajališta stroge formalnosti, ova preformulacija nema previše smisla, budući da pretpostavlja da su koncepti "istinitog" i "neistinitog" definirani u apsolutnom smislu, a ne u relativnom za svaki određeni sustav.