Gödelov teorem o nepotpunosti u jednostavnim terminima. Zanimljivosti i korisni savjeti

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 takvih jednostavni zadaci, čiji se odgovor čini očitim dok ne zagrebete malo dublje. razgovarajući moderni jezik, to je bilo pitanje: je li matematika dovoljna sama po sebi? 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 mozak nadmašuje računalo okovano čistim logički sklopovi. 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 Princeton napredna istraživanja. 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.

Dugo me zanimalo što je senzacionalni Gödelov teorem. I koliko je to korisno za život. I konačno sam to uspio shvatiti.

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

Ja bih to ovako preveo na ljudski nematematički jezik (aksiom je početno stajalište teorije, prihvaćeno u okviru te teorije kao istinito bez potrebe za dokazivanjem i korišteno kao osnova za dokazivanje ostalih njezinih odredbi). U životu, aksiom su načela koja slijedi osoba, društvo, znanstveni smjer, Države. Među predstavnicima religije aksiomi se nazivaju dogmama. Posljedično, svaki naš princip, bilo koji sustav pogleda, počevši od određene razine, postaje interno proturječan, ili nedovršen. Da bi se netko uvjerio u istinitost određene tvrdnje, morat će izaći iz okvira zadanog sustava stajališta i izgraditi novi. Ali bit će i nesavršeno. Odnosno, PROCES SPOZNAJE JE BESKONAČAN. Svijet se ne može u potpunosti spoznati dok ne dođemo do izvora.

"... ako sposobnost logičkog rasuđivanja smatramo glavnom karakteristikom ljudskog uma, ili barem njegovim glavnim alatom, onda Gödelov teorem izravno ukazuje na ograničene mogućnosti našeg mozga. Složite se da je vrlo teško osobi koja je dovela na vjeri u beskrajnu moć misli prihvatiti tezu o granicama njezine moći... Mnogi stručnjaci vjeruju da su formalno-komputacijski, "aristotelovski" procesi u pozadini logično mišljenje, samo su dio ljudska svijest. Njegovo drugo područje, u osnovi "nekompjutersko", odgovorno je za takve manifestacije kao što su intuicija, kreativni uvidi i razumijevanje. I ako prva polovica uma potpada pod Gödelova ograničenja, onda je druga polovica slobodna od takvih ograničenja ... Fizičar Roger Penrose otišao je još dalje. Predložio je postojanje nekih kvantnih učinaka nekomputacijske prirode, koji osiguravaju realizaciju kreativnih činova svijesti... Jedna od mnogih posljedica Penroseove hipoteze može biti, posebice, zaključak da umjetna inteligencija na temelju suvremenih računalnih uređaja, čak i ako će pojava kvantnih računala dovesti do grandioznog proboja u području računalne tehnologije. Činjenica je da svako računalo može samo sve točnije modelirati rad formalno-logičke, „računske“ aktivnosti ljudske svijesti, ali su mu nedostupne „neračunalne“ sposobnosti intelekta.

Jedna važna posljedica Gödelovog teorema je zaključak da se ne može razmišljati u krajnostima. Uvijek unutar postojeća teorija postoji izjava koja se ne može ni dokazati ni opovrgnuti. Ili, drugim riječima, za neku tvrdnju uvijek postoji par koji je opovrgava.

Sljedeći zaključak. Dobro i zlo su samo dvije strane istog novčića, bez kojih ne može postojati. A proizlazi iz principa da u Svemiru postoji samo jedan izvor svega: dobra i zla, ljubavi i mržnje, života i smrti.

Svaka izjava o cjelovitosti sustava je lažna. Ne možete se oslanjati na dogme, jer će prije ili kasnije biti opovrgnute.

U tom su smislu moderne religije u kritičnom položaju: dogme crkve suprotstavljaju se razvoju naših ideja o svijetu. Sve pokušavaju ugurati u okvire krutih koncepata. Ali to vodi do činjenice da iz monoteizma, iz jednog izvora svega prirodni procesi prelaze u poganstvo, gdje postoje sile dobra i sile zla, postoji bog dobra negdje daleko na nebu, i postoji vrag (bog zla), koji je odavno stavio šapu na sve što je na Zemlji. Ovakav pristup dovodi do podjele svih ljudi na prijatelje i neprijatelje, pravednike i grešnike, vjernike i heretike, prijatelje i neprijatelje.

Evo još jednog malog teksta koji popularno otkriva bit koja proizlazi iz Gödelovog teorema:
“Čini mi se da ovaj teorem nosi važan filozofsko značenje. Moguće su samo dvije opcije:

a) Teorija je nepotpuna, tj. u smislu teorije, može se formulirati pitanje na koje je nemoguće izvesti bilo pozitivan ili negativan odgovor iz aksioma/postulata teorije. Istodobno, odgovori na sva takva pitanja mogu se dati u okviru opsežnije teorije, u kojoj će stara biti poseban slučaj. Ali ovo nova teorija imat će svoja "pitanja bez odgovora" i tako u nedogled.

b) Potpun, ali kontradiktoran. Na bilo koje pitanje može se odgovoriti, ali na neka se pitanja može odgovoriti i s da i s ne u isto vrijeme.

Znanstvene teorije su prve vrste. Dosljedni su, ali to znači da ne opisuju sve. Ne može biti "konačnog" znanstvena teorija. Svaka teorija je nepotpuna i ne opisuje nešto, čak i ako još ne znamo što je to. Može se samo stvarati sve opsežnije teorije. Za mene osobno to je razlog za optimizam, jer to znači da napredak znanosti nikada neće stati.

"Svemogući Bog" pripada drugoj vrsti. Svemogući Bog je odgovor na svako pitanje. A to automatski znači da vodi u logički apsurd. Paradoksi poput "teškog kamena" mogu se izmišljati u serijama.

Sve u svemu, znanstveno znanje je istinit (dosljedan), ali u bilo kojem trenutku ne opisuje sve. Istovremeno, ništa ne sprječava pomicanje granica poznatog u beskraj, sve dalje i dalje i prije ili kasnije svako nepoznato postaje poznato. Religija tvrdi da Potpuni opis svijetu "upravo sada", ali je automatski netočno (apsurdno)."

Jednom, kad sam tek počinjao svoj odrasli život Programirao sam. I postojao je takav princip: ako se u program unese mnogo ispravaka, mora se ponovno napisati. Ovaj princip, po mom mišljenju, odgovara Godelovom teoremu. Ako program postaje složeniji, postaje nedosljedan. I neće raditi kako treba.

Još jedan primjer iz života. Živimo u eri kada dužnosnici govore da bi glavni princip postojanja trebao biti zakon. Odnosno pravni sustav. Ali čim zakonodavstvo postane složenije i stvaranje pravila procvjeta, zakoni počinju proturječiti jedni drugima. Ono što sada vidimo. Nikada ne možete stvarati legalni sistem, koji bi propisivao sve aspekte života. S druge strane, bilo bi pošteno za sve. Jer ograničenja našeg razumijevanja svijeta uvijek će izaći na vidjelo. I ljudski zakoni će u nekom trenutku početi dolaziti u sukob sa zakonima svemira. Mnoge stvari razumijemo intuitivno. Također intuitivno, moramo prosuđivati ​​postupke drugih ljudi. Dovoljno je da država ima ustav. I oslanjajući se na članke ovog ustava, urediti odnose u društvu. No, prije ili kasnije, ustav će se morati promijeniti.

USE je još jedan primjer pogrešnosti naših ideja o ljudskim sposobnostima. Pokušavamo ispitati računalne sposobnosti mozga na ispitu. Ali intuitivne sposobnosti u školi su se prestale razvijati. Ali čovjek nije biorobot. Nemoguće je stvoriti sustav bodovanja koji bi mogao otkriti sve mogućnosti koje su svojstvene čovjeku, u njegovoj svijesti, u njegovoj podsvijesti iu njegovoj psihi.

Prije gotovo 100 godina Gödel je napravio nevjerojatan korak u razumijevanju zakona svemira. I još uvijek nismo bili u mogućnosti to koristiti, smatrajući ovaj teorem visoko specijaliziranim matematički problem za uski krug ljudi koji se u svom krugu bave nekim apstraktnim temama. Zajedno s kvantna teorija i Kristova učenja, Gödelov nam teorem omogućuje bijeg iz zatočeništva lažnih dogmi, prevladavanje krize koja još uvijek traje u našem svjetonazoru. A vrijeme curi.

Jedan od naj poznati teoremi matematička logika, sreća i nesreća u isto vrijeme. U ovome je ona kao posebna teorija Einsteinova relativnost. 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.

Pojednostavljeno, TGN tvrdi da je to dovoljno teški jezici ima neutemeljenih izjava. 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 nekima poznata pravila. 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 po konačan broj korake 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, kad smo poučeni školska matematika, tada se ponekad stvara pogrešan dojam o gotovo potpunoj istovjetnosti fraza "teorem je istinit" i "teorem je moguće dokazati ili provjeriti". 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 prikazuju set realni brojevi u nju, onda "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čan rezultat, iako mu se može približiti koliko god želite - 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 opisujemo jezik formalna aritmetika". Razmotrimo klasu tekstualnih nizova konačne duljine, koji se sastoje od arapskih brojeva, varijabli (slova latinica), uzimajući prirodne vrijednosti, razmake, znakove aritmetičke operacije, jednakost i nejednakost, kvantifikatore (“postoji”) i (“za bilo koga”) i, možda, još neke simbole (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 slijede dvoslovne formule itd.; po kojoj će se abecedi redoslijed odvijati nije nam bitno). 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:

• „Bilo koja fraza kineski istinita je 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?

Oznake: Dodajte oznake

09sen

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 David Gilbert(David Hilbert, 1862.–1943.) u obliku teza ocrtao je 23 najvažnija, po njegovu mišljenju, zadatka koja su teoretičari nadolazećeg dvadesetog stoljeća morali riješiti. 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? Drugi Hilbertov zadatak svodio se na potrebu strogog dokazivanja da je sustav aksioma - osnovnih iskaza koji se u matematici uzimaju kao osnova bez dokaza - savršen i potpun, odnosno da omogućuje matematički opis svega š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. U standardnoj euklidskoj planimetriji (geometriji na ravnini) može se bezuvjetno dokazati da je istinita tvrdnja da je zbroj kutova trokuta 180°, a da je zbroj kutova trokuta 137°. "je lažno. 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 1931. neki bečki matematičar s naočalama Kurt Gödel- 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". Dakle, Gödel je jednostavno dokazao sljedeće nevjerojatno svojstvo bilo kojeg sustava 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 nije dokaziva", onda je moguće dokazati i valjanost tvrdnje "Pretpostavka 247 je dokaziva". 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. Odnosno, moramo se pomiriti s činjenicom da ćemo u kontekstu bilo kojeg logičkog sustava i dalje imati izjave tipa A koje su očito istinite ili netočne, a njihovu istinitost možemo prosuđivati ​​samo izvan okvira aksiomatike koju imamo usvojeni. 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 Gödelovog prvog ili slabog teorema o nepotpunosti je: "Svaki formalni sustav aksioma sadrži nerazriješene pretpostavke". Ali Gödel nije tu stao, formulirajući i dokazujući Gödelov drugi ili jaki 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 Gödelovi teoremi može se koristiti za dokazivanje postojanja 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, a Turingov test će proći.

na temu: "GODELOV TEOREM"

Kurt Gödel

Kurt Gödel je najveći stručnjak za matematička logika- 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 Princeton visoke studije. Gödel, počasni doktorat sa sveučilišta Yale i Harvard, suradnik Nacionalna akademija Sciences of the United States i American Philosophical Society.

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 klasičnih logičkih rečenica na njihove intuicionističke dvojnike, što je postavilo temelj za sustavnu upotrebu "operacija uranjanja" koje omogućuju takvo smanjenje različitih logički sustavi jedni druge), formalna aritmetika (1932. – 1933.; rezultati o mogućnosti redukcije klasične aritmetike na intuicionističku aritmetiku, pokazujući na neki način konzistentnost prve s obzirom na drugu), teorija algoritama i rekurzivnih funkcija (1934.; definicija koncepta opće rekurzivne funkcije, koja je igrala odlučujuću ulogu u utvrđivanju algoritamske nerješivosti niza kritična pitanja matematika 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 serije ključni rezultati o relativnoj dosljednosti i neovisnosti skupovno-teorijskih principa).

Godelov teorem o nepotpunosti

Uvod

1931. u jednoj od njem znanstvenih časopisa pojavio se relativno kratak rad s prilično zastrašujućim naslovom "O formalno neodlučivim tvrdnjama 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šte Harvard dodijelivši Gödelu počasni doktorat (1952.), opisana je kao jedna od najveća postignuća moderna logika.

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; upoznatost s traktatom nikako nije bila 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» izjave, od kojih se za neke pretpostavlja da su istinite bez dokaza (takve se izjave nazivaju aksiomi), dok se druge (teoremi) mogu izvesti iz aksioma, pa se stoga pretpostavlja (dokazuje) da su istinite. 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 ( kompjuterski program) koji (ako mu se dopusti izračunavanje proizvoljno dugih vremena, do beskonačnosti) izračunava 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 teorije, onda bi teorija sadržavala teorem koji je sam sebi proturječan, i stoga bi teorija bila nedosljedna. Ali ako G nedokaziva, onda je istinita, pa je stoga teorija nepotpuna (izjava G nije izvodljivo u njemu).

Ovo je objašnjenje uobičajeno prirodni jezik, i stoga nije sasvim matematički rigorozan. Kako bi pružio rigorozan dokaz, Gödel je numerirao izjave s prirodni brojevi. U ovom slučaju, teorija koja opisuje brojeve također pripada skupu propozicija. Pitanja o dokazivosti iskaza mogu se predstaviti u ovaj slučaj u obliku 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 (to jest, učinkovito generiranu) teoriju T, uključujući osnovne aritmetičke izjave o istini i određene formalne izjave o dokazivosti, ovu teoriju T uključuje izjavu o svojoj dosljednosti ako i samo ako je teorija T nekonzistentna.

Drugim riječima, dosljednost je dovoljna bogata teorija ne može se dokazati ovom teorijom. 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. Nešto drugačiji pristup ima Roger Penrose, koji je u knjizi prezentiran potpuno, "od nule".

Rasprave

Posljedice teorema utječu na filozofiju matematike, posebno na one formalizme koji koriste formalna logika da definiraju svoje principe. 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 se koncepti "istinitog" i "lažnog" definiraju u apsolutnom smislu, a ne u relativnom. svaki specifičan sustav.