Gedelov teorem o nepotpunosti jednostavnim riječima. Zanimljive činjenice i korisni savjeti

Svaki sistem matematičkih aksioma, počevši od određenog nivoa složenosti, ili je interno 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 teoretičari. narednog dvadesetog veka. Broj dva na njegovoj listi bio je jedan od njih jednostavni zadaci, odgovor na koji se čini očiglednim dok ne zadubite malo dublje. razgovor savremeni jezik, to je bilo pitanje: da li je matematika dovoljna sama po sebi? Hilbertov drugi problem je bio da rigorozno dokaže da je sistem aksiome- osnovni iskazi uzeti u matematici kao osnova bez dokaza - savršen je i potpun, odnosno omogućava vam da matematički opišete sve što postoji. Bilo je potrebno dokazati da je moguće postaviti takav sistem aksioma koji će, prvo, biti međusobno konzistentni, a drugo, iz njih se može izvući zaključak o istinitosti ili neistinitosti bilo koje tvrdnje.

Uzmimo primjer iz školske geometrije. Standard Euklidska planimetrija(geometrija na ravni) moguće je bezuslovno dokazati da je tvrdnja "zbir uglova trougla 180°" tačna, a tvrdnja "zbir uglova trougla je 137°" netačna. U suštini, u euklidskoj geometriji, svaka izjava je ili lažna ili istinita, a treća nije data. A početkom dvadesetog veka matematičari su naivno verovali da istu situaciju treba posmatrati u svakom logički doslednom sistemu.

A onda je 1931. neki bečki matematičar Kurt Godel s naočalama uzeo i objavio kratak članak koji je jednostavno preokrenuo cijeli svijet takozvane "matematičke logike". Nakon dugih i složenih matematičkih i teorijskih preambula, on je doslovno ustanovio sljedeće. Uzmimo bilo koju izjavu poput: "Pretpostavka #247 je logički nedokaziva u ovom sistemu aksioma" i nazovimo je "tvrdnjom A". Tako je Gödel jednostavno dokazao sljedeće nevjerovatno svojstvo bilo koji aksiomski sistemi:

"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“, onda je moguće dokazati valjanost tvrdnje „Pretpostavka 247 dokazano". Odnosno, vraćajući se na formulaciju drugog Hilbertovog problema, ako je sistem aksioma potpun (tj. bilo koja izjava u njemu može biti dokazana), onda je nedosljedan.

Jedini izlaz iz ove situacije je prihvatanje nekompletnog sistema aksioma. Odnosno, moramo da se pomirimo sa činjenicom da će nam u kontekstu bilo kog logičkog sistema ostati iskazi tipa A koji su očigledno tačni ili netačni - i možemo suditi samo o njihovoj istinitosti vani okvir aksiomatike koju smo usvojili. Ako takvih tvrdnji nema, onda je naša aksiomatika kontradiktorna, au njenom okviru će se neizbježno naći formulacije koje se mogu i dokazati i opovrgnuti.

Dakle, formulacija prvo,or slab Gedelove teoreme o nepotpunosti: "Svaki formalni sistem aksioma sadrži neriješene pretpostavke." Ali Gödel nije stao na tome, formulirajući i dokazujući sekunda, ili jaka Godelova teorema o nepotpunosti: „Logička potpunost (ili nepotpunost) bilo kojeg sistema aksioma ne može se dokazati u okviru ovog sistema. Da bi se to dokazalo ili opovrglo, potrebni su dodatni aksiomi (jačanje sistema).

Bilo bi sigurnije misliti da su Godelove teoreme apstraktne i da se ne tiču ​​nas, već samo područja uzvišene matematičke logike, ali se u stvari pokazalo da su u direktnoj vezi sa strukturom ljudskog mozga. Engleski matematičar i fizičar Roger Penrose (rođen 1931.) pokazao je da se Gedelove teoreme mogu koristiti za dokazivanje fundamentalnih razlika između ljudskog mozga i kompjutera. Poenta njegovog rezonovanja je jednostavna. Kompjuter radi strogo logički i nije u stanju da utvrdi da li je izjava A tačna ili netačna ako izlazi iz okvira aksiomatike, a takvi iskazi, prema Gödelovoj teoremi, neizbežno postoje. Osoba, suočena sa tako logički nedokazivom i nepobitnom tvrdnjom A, uvijek je u stanju da utvrdi njenu istinitost ili neistinitost – na osnovu svakodnevnog iskustva. Barem u ovome ljudski mozak nadmašuje računar okovan čistim logička kola. Ljudski mozak je u stanju da shvati punu dubinu istine sadržanu u Gedelovim teoremama, ali kompjuter nikada ne može. Stoga je ljudski mozak sve samo ne kompjuter. On je sposoban donositi odluke, i Turingov test će proći.

Pitam se da li je Hilbert imao pojma dokle će nas njegova pitanja odvesti?

Kurt Godel, 1906-78

austrijski, zatim američki matematičar. Rođen u Brünnu (Brünn, sada Brno, Češka). Diplomirao je na Univerzitetu u Beču, gdje je ostao nastavnik na Odsjeku za matematiku (od 1930. - profesor). Godine 1931. objavio je teoremu koja je kasnije dobila njegovo ime. Kao čisto apolitična osoba, izuzetno je teško preživio ubistvo svog prijatelja i službenika odjela od strane nacističkog studenta i pao u duboku depresiju čiji su ga recidivi pratili do kraja života. 1930-ih emigrirao je u Sjedinjene Države, ali se vratio u rodnu Austriju i oženio. 1940. godine, na vrhuncu rata, bio je prisiljen pobjeći u Ameriku u tranzitu kroz SSSR i Japan. Radio je neko vrijeme na Princeton institutu napredno istraživanje. Nažalost, psiha naučnika 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 zanima šta je senzacionalna Gödelova teorema. I koliko je to korisno za život. I konačno sam to mogao shvatiti.

Najpopularnija formulacija teoreme je:
"Svaki sistem matematičkih aksioma, počevši od određenog nivoa složenosti, ili je interno nedosledan ili nekompletan."

Preveo bih to na ljudski nematematički jezik kao što je ovaj (aksiom je početna pozicija teorije, prihvaćena u okviru ove teorije kao istinita bez dokazivanja i korištena kao osnova za dokazivanje ostalih njenih odredbi). U životu, aksiom su principi koje slijedi osoba, društvo, naučni pravac, navodi. Među predstavnicima religije, aksiomi se nazivaju dogmama. Shodno tome, bilo koji naš princip, bilo koji sistem pogleda, počevši od određenog nivoa, postaje interno kontradiktoran, ili nepotpun. Da bi se uvjerio u istinitost određene tvrdnje, morat će se ići dalje od datog sistema pogleda i izgraditi novi. Ali će takođe biti nesavršen. Odnosno, PROCES ZNANJA JE BESKONAČAN. Svijet ne može biti potpuno poznat dok ne dođemo do izvora.

"... ako sposobnost logičkog zaključivanja smatramo glavnom karakteristikom ljudskog uma, ili barem njegovim glavnim oruđem, onda Gedelova teorema direktno ukazuje na ograničene mogućnosti našeg mozga. na vjeri u beskonačnu moć misli da prihvati tezu o granicama njene moći... Mnogi stručnjaci vjeruju da su formalno-računarski, "aristotelovski" procesi u osnovi logičko razmišljanje, samo su dio ljudska svijest. Njegovo drugo područje, u osnovi „neračunarsko“, odgovorno je za takve manifestacije kao što su intuicija, kreativni uvidi i razumijevanje. A ako prva polovina uma potpada pod Gödelova ograničenja, onda je druga polovina oslobođena takvih ograničenja... Fizičar Roger Penrose otišao je još dalje. On je sugerirao postojanje nekih kvantnih efekata ne-računarske prirode, koji osiguravaju realizaciju kreativnih činova svijesti... Jedna od mnogih posljedica Penroseove hipoteze može biti, posebno, zaključak da umjetna inteligencija na bazi savremenih računarskih uređaja, čak i ako će pojava kvantnih računara dovesti do grandioznog prodora u oblasti računarske tehnologije. Činjenica je da svaki kompjuter može samo sve preciznije modelirati rad formalno-logičke, "računarske" aktivnosti ljudske svijesti, ali su mu "neračunarske" sposobnosti intelekta nedostupne.

Jedna važna posljedica Gödelove teoreme je zaključak da se ne može razmišljati u ekstremima. Uvek unutra postojeća teorija postoji izjava koja se ne može ni dokazati ni opovrgnuti. Ili, drugim riječima, za neku izjavu uvijek postoji par koji je opovrgava.

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

Svaka izjava o kompletnosti sistema je lažna. Ne možete se osloniti na dogme, jer će one prije ili kasnije biti opovrgnute.

U tom smislu, moderne religije su u kritičnoj poziciji: crkvene dogme se suprotstavljaju razvoju naših ideja o svijetu. Pokušavaju sve stisnuti u okvire krutih koncepata. Ali to dovodi do činjenice da iz monoteizma, iz jednog izvora svega prirodni procesi prelaze na paganizam, gdje postoje sile dobra i sile zla, postoji bog dobra negdje daleko na nebu, a postoji i đavo (bog zla), koji je odavno položio svoju šapu na sve što je na Zemlji. Ovakav pristup dovodi do podjele svih ljudi na prijatelje i neprijatelje, pravednike i grešnike, vjernike i jeretike, prijatelje i neprijatelje.

Evo još jednog malog teksta koji popularno otkriva suštinu koja proizlazi iz Gödelove teoreme:
„Čini mi se da ova teorema nosi važnu filozofsko značenje. Moguće su samo dvije opcije:

a) Teorija je nepotpuna, tj. u terminima teorije, može se formulisati pitanje na koje je nemoguće izvući ni pozitivan ni negativan odgovor iz aksioma/postulata teorije. Istovremeno, odgovori na sva ovakva pitanja mogu se dati u okviru jedne opsežnije teorije, u kojoj će stara biti poseban slučaj. Ali ovo nova teorijaće imati svoja "pitanja bez odgovora" i tako dalje do beskonačnosti.

b) Potpuna, ali kontradiktorna. Na bilo koje pitanje se može odgovoriti, ali na neka pitanja se može odgovoriti i sa da i ne u isto vrijeme.

Naučne teorije su prve vrste. One su dosljedne, ali to znači da ne opisuju sve. Ne može biti "finala" naučna teorija. Svaka teorija je nekompletna i ne opisuje nešto, čak i ako još ne znamo šta je to. Može se samo stvarati sve obuhvatnije teorije. Za mene lično, ovo je razlog za optimizam, jer to znači da napredak nauke 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 izmisliti u serijama.

Sve u svemu, naučna saznanja je istinit (dosljedan), ali u bilo kojem trenutku ne opisuje sve. Istovremeno, ništa ne sprečava pomeranje granica poznatog u beskonačnost, sve dalje i dalje i pre ili kasnije svako nepoznato postaje poznato. Religija tvrdi da Puni opis svijet "trenutno", ali je to automatski netačno (apsurdno)."

Svojevremeno, kada sam tek počinjao odraslog života Programirao sam. I postojao je takav princip: ako se napravi mnogo ispravki u programu, mora se ponovo napisati. Ovaj princip, po mom mišljenju, odgovara Godelovoj teoremi. Ako program postane složeniji, postaje nedosljedan. I neće raditi kako treba.

Još jedan primjer iz života. Živimo u eri kada zvaničnici kažu da glavni princip postojanja treba da bude zakon. Odnosno, pravni sistem. Ali čim zakonodavstvo postane složenije i donošenje pravila procvjeta, zakoni počinju da su u suprotnosti jedni s drugima. Ono što sada vidimo. Nikada ne možete stvarati legalni sistem, koji bi propisao sve aspekte života. S druge strane, bilo bi fer za sve. Zato što će ograničenja našeg razumijevanja svijeta uvijek izaći na vidjelo. I ljudski zakoni će u jednom trenutku početi da se sukobljavaju sa zakonima univerzuma. Mnoge stvari razumijemo intuitivno. Takođe intuitivno, moramo suditi o postupcima drugih ljudi. Dovoljno je da država ima ustav. I oslanjajući se na članove ovog ustava, urediti odnose u društvu. Ali prije ili kasnije, ustav će se morati promijeniti.

USE je još jedan primjer pogrešnosti naših ideja o ljudskim sposobnostima. Pokušavamo testirati računske sposobnosti mozga na ispitu. Ali intuitivne sposobnosti u školi su prestale da se razvijaju. Ali čovjek nije biorobot. Nemoguće je stvoriti sistem bodovanja koji bi mogao otkriti sve mogućnosti koje su inherentne čovjeku, njegovoj svijesti, njegovoj podsvijesti i njegovoj psihi.

Prije skoro 100 godina, Gödel je napravio nevjerovatan korak u razumijevanju zakona univerzuma. I još uvijek to nismo mogli koristiti, smatrajući ovu teoremu visoko specijaliziranom matematički problem za uski krug ljudi koji se bave nekim apstraktnim temama u svom krugu. Zajedno sa kvantna teorija i Hristovog učenja, Gedelova teorema nam omogućava da pobegnemo iz zatočeništva lažnih dogmi, da prevaziđemo krizu koja još uvek postoji u našem pogledu na svet. A vrijeme ističe.

Jedan od mnogih poznate teoreme matematička logika, srećna i nesrećna u isto vreme. U ovome je ona kao specijalna teorija Ajnštajnova relativnost. S jedne strane, skoro svi su čuli nešto o njima. S druge strane, u popularnoj interpretaciji, Ajnštajnova teorija, kao što znate, "kaže da je sve na svetu relativno". I Gedelov teorem o nepotpunosti (u daljem tekstu jednostavno TGN), u približno jednako slobodnoj narodnoj formulaciji, "dokazuje da postoje stvari koje su 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 da obje strane ne mogu biti u pravu u isto vrijeme, već i da se ni jedna ni druga ne trude da dokuče šta, u stvari, ova teorema kaže.

Pa šta? U nastavku ću pokušati da "na prste" pričam o tome. Moje izlaganje, naravno, neće biti rigorozno i ​​intuitivno, ali ću zamoliti matematičare da me ne osuđuju striktno. Moguće je da će za nematematičare (kojima, u stvari, i ja pripadam), biti nešto novo i korisno u onome što je rečeno u nastavku.

Matematička logika je zaista prilično komplikovana nauka, i što je najvažnije, nije baš poznata. Zahtijeva pažljive i stroge manevre, u kojima je važno ne pobrkati stvarno dokazano sa činjenicom da je "već jasno". Međutim, nadam se da će čitaocu za razumijevanje sljedećeg “crta dokaza TGN-a” biti potrebno samo znanje školske matematike/informatike, vještine logičkog razmišljanja i 15-20 minuta vremena.

Pojednostavljujući donekle, TGN tvrdi da je to dovoljno teški jezici postoje nepotkrijepljene izjave. Ali u ovoj frazi, gotovo svaka riječ treba objašnjenje.

Počnimo pokušavajući da shvatimo šta je dokaz. Uzmimo neki školski zadatak iz aritmetike. Na primjer, neka se traži da se dokaže ispravnost sljedeće jednostavne formule: "" (podsjećam da se simbol čita "za bilo koji" i zove se "univerzalni kvantifikator"). To se može dokazati identičnom transformacijom, recimo, ovako:

Prelazak s jedne formule na drugu se događa prema nekima poznata pravila. Prijelaz sa 4. formule na 5. dogodio se, recimo, zato što je svaki broj jednak samom sebi - takav je aksiom aritmetike. I cijeli postupak dokazivanja, dakle, prevodi formulu u logičku vrijednost TRUE. Rezultat bi mogao biti LAŽAN - ako bismo opovrgli neku formulu. U ovom slučaju bismo dokazali njegovu negaciju. Moguće je zamisliti program (a 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, a postoje pravila po kojima je podskup tzv. izjave- odnosno gramatički značajne fraze, od kojih je svaka istinita ili netačna. Možemo reći da postoji funkcija koja odgovara iskazima iz jedne od dvije vrijednosti: TRUE ili FALSE (to jest, preslikava ih na Boolean skup od dva elementa).

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

Za ono što slijedi, potreban nam je pojam algoritma. Neću ovdje davati njegovu formalnu definiciju - to bi nas odvelo prilično u stranu. Ograničiću se na neformalno: "algoritam"- ovaj niz nedvosmislenih instrukcija ("program"), koji per konačan broj stepenice 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 u primjeni na naš slučaj, čitalac može smatrati da je algoritam program napisan u bilo kojem njemu poznatom programskom jeziku, za koji je zagarantovano da će za bilo koji ulazni podatak iz date klase završiti svoj rad s Booleovim rezultatom.

Zapitajmo se: postoji li “algoritam dokazivanja” za svaku funkciju (ili, ukratko, "deduktivan") ekvivalentno ovoj funkciji, odnosno prevođenje svake izjave u potpuno istu logičku vrijednost kao i ona? Konciznije, isto pitanje se može formulirati na sljedeći način: da li je svaka funkcija nad skupom propozicija izračunljiv? Kao što već možete pretpostaviti, iz valjanosti TGN-a proizilazi 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 izazvati vaš interni protest. To je zbog nekoliko okolnosti. Prvo, kada nas nauče skolska matematika, onda se ponekad stvara lažan utisak o gotovo potpunom identitetu fraza "teorema je istinita" i "teorema je moguće dokazati ili potvrditi". Ali ako razmislite o tome, to uopće nije očigledno. Neke teoreme se dokazuju prilično jednostavno (na primjer, nabrajanjem malog broja opcija), a neke su vrlo teške. Razmotrimo, na primjer, Fermatovu čuvenu Posljednju teoremu:

čiji je dokaz pronađen tek tri i po stoljeća nakon prve formulacije (i daleko je od elementarnog). Potrebno je razlikovati istinitost iskaza i njegovu dokazivost. Ni od kuda ne proizlazi da ne postoje istinite, već nedokazive (i ne u potpunosti provjerljive) izjave.

Drugi intuitivni argument protiv TGN-a je suptilniji. Pretpostavimo da imamo neku nedokazivu (u okviru ove deduktivne) tvrdnje. Šta nas sprečava da to prihvatimo kao novi aksiom? Tako ćemo malo zakomplikovati naš sistem dokaza, ali to nije strašno. Ovaj argument bi bio savršeno tačan da postoji 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 - naići ćete na treći. I tako u nedogled. Kažu da će deductica ostati nepotpuno. Također možemo poduzeti snažne mjere tako da se algoritam za dokazivanje završi nakon konačnog broja koraka s nekim rezultatom za bilo koju izjavu jezika. Ali u isto vrijeme, on će početi lagati - dovesti do istine za netačne izjave, ili do laži - za vjernike. U takvim slučajevima se kaže da je deduktivan kontradiktorno. Dakle, još jedna formulacija TGN-a zvuči ovako: "Postoje propozicijski jezici za koje je potpuna konzistentna deduktika nemoguća" - otuda i naziv teoreme.

Ponekad se naziva i "Gödelov teorem" tvrdnja da bilo koja teorija sadrži probleme koji se ne mogu riješiti unutar okvira same teorije i zahtijevaju njenu generalizaciju. U određenom smislu to je tačno, iako takva formulacija zamagljuje problem, a ne razjašnjava ga.

Također napominjem da ako govorimo o uobičajenim funkcijama koje prikazuju skup realni brojevi u njega, 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 veliku sreću s argumentom tako da se proces izračunavanja točne decimalne reprezentacije vrijednosti ove funkcije završava u konačnom broju koraka. I najvjerovatnije ćete ga izračunati koristeći beskonačan niz, a ovo izračunavanje nikada neće dovesti do toga tač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 nizovi i čije su vrijednosti nula ili jedan, neizračunljive funkcije, iako su 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 dužine, koja se sastoji od arapskih brojeva, varijabli (slova latinica), uzimajući prirodne vrijednosti, razmake, znakove aritmetičke operacije, jednakost i nejednakost, kvantifikatori („postoji“) i („za bilo koje“) i, možda, neki drugi simboli (njihov tačan broj i sastav su za nas 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 netačni u smislu obične aritmetike) biće naš skup iskaza.

Primjeri formalnih aritmetičkih iskaza:

itd. Sada nazovimo "formulu sa slobodnim parametrom" (FSP) stringom koji postaje izraz ako se u njega kao ovaj parametar unese prirodni broj. Primjeri FSP-a (sa parametrom):

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

Skup svih FSP-ova označiti slovom . Jasno je da se može poređati (na primjer, prvo ispisujemo jednoslovne formule poredane po abecednom redu, zatim formule od dva slova, itd.; po kojem će se abecedi redoslijed odvijati nije nam bitno). Dakle, bilo koji FSP odgovara svom broju na uređenoj listi, a mi ćemo ga označiti .

Pređimo sada na skicu dokaza TGN-a u sljedećoj formulaciji:

• Za propozicioni jezik formalne aritmetike ne postoji potpuna konzistentna dedukcija.

Dokazaćemo kontradikcijom.

Dakle, pretpostavimo da takav deduktiv postoji. Hajde da opišemo sledeći pomoćni algoritam koji prirodnom broju dodeljuje booleovu vrednost na sledeći način:

Jednostavno rečeno, algoritam daje vrijednost TRUE ako i samo ako rezultat zamjene u FSP vlastiti broj na našoj listi daje lažnu izjavu.

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

Očigledno, pod gornjom pretpostavkom, bilo koji FSP iz može biti povezan s algoritmom koji sadrži prirodni broj na ulazu i Booleovu vrijednost na izlazu. Manje očigledno je suprotno:

Dokaz ove leme zahtijevao bi barem formalnu, a ne intuitivnu definiciju pojma algoritma. Međutim, ako malo razmislite, prilično je uvjerljivo. Zaista, algoritmi su napisani na algoritamskim jezicima, među kojima ima i egzotičnih kao što je, na primjer, Brainfuck, koji se sastoji od osam riječi od jednog znaka, u kojima se, ipak, može implementirati bilo koji algoritam. Bilo bi čudno kada bi se bogatiji jezik formalnih aritmetičkih formula koji smo opisali pokazao lošijim - iako, bez sumnje, nije baš pogodan za obično programiranje.

Nakon prolaska ovog klizavog mjesta, brzo dolazimo do kraja.

Dakle, gore smo opisali algoritam. Prema lemi u koju sam vas zamolio da vjerujete, postoji ekvivalentni FSP. Ima neki broj na listi - recimo. Zapitajmo se šta je poenta? Neka bude ISTINA. Zatim, prema konstrukciji algoritma (a time i funkciji koja mu je ekvivalentna), to znači da je rezultat zamjene broja u funkciju FALSE. Na isti način se provjerava suprotno: iz FALSE slijedi TRUE. Došli smo do kontradikcije, što znači da je prvobitna pretpostavka pogrešna. Dakle, za formalnu aritmetiku ne postoji potpuna konzistentna dedukcija. Q.E.D.

Ovdje je prikladno podsjetiti se na Epimenida (vidi portret u naslovu), koji je, kao što znate, izjavio da su svi Krićani lažovi, budući da je i sam Krićanin. U sažetijoj formulaciji, njegova izjava (poznata kao "paradoks lažova") može se formulisati kao: "Lažem". Upravo takvu tvrdnju, koja sama proglašava svoju neistinitost, koristili smo za dokaz.

U zaključku, ž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 predstaviti kao omjer dva cijela broja (zapamtite, ova izjava ima vrlo elegantan dokaz star više od dvije hiljade godina?). I korijeni polinoma s racionalnim koeficijentima također nisu svi brojevi. A sada se pokazalo da nisu sve funkcije prirodnog argumenta izračunljive.

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

• „Bilo koja fraza Kineski je istinita izjava ako je sadržana u citatniku druga Mao Tse Tunga, a netačna je ako nije sadržana.

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

• “Prelistajte citate druga Mao Tse Tunga dok ne pronađete izjavu koju tražite. Ako se nađe, onda je tačno, a ako je citatnik gotov, a izjava nije pronađena, onda je lažna.

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

Oznake: Dodajte oznake

09sen

Svaki sistem matematičkih aksioma, počevši od određenog nivoa složenosti, ili je interno nekonzistentan ili nepotpun.

Godine 1900. održana je Svjetska konferencija matematičara u Parizu, gdje je David Gilbert(David Hilbert, 1862–1943) je u formi teza iznio 23 najvažnija, po njegovom mišljenju, zadatka koje su teoretičari nadolazećeg dvadesetog vijeka morali riješiti. Broj dva na njegovoj listi bio je jedan od onih jednostavnih problema koji se čine očiglednim dok ne zakopate malo dublje. U modernim terminima, to je bilo pitanje: da li je matematika dovoljna sama po sebi? Hilbertov drugi zadatak svodio se na potrebu da se striktno dokaže da je sistem aksioma – osnovnih tvrdnji koje se u matematici uzimaju kao osnova bez dokaza – savršen i potpun, odnosno da omogućava matematički opis svega što postoji. Bilo je potrebno dokazati da je moguće postaviti takav sistem aksioma koji će, prvo, biti međusobno konzistentni, a drugo, iz njih se može izvući zaključak o istinitosti ili neistinitosti bilo koje tvrdnje.

Uzmimo primjer iz školske geometrije. U standardnoj euklidskoj planimetriji (geometrija na ravni) može se bezuslovno dokazati da je tvrdnja "zbir uglova trougla 180°" tačna, a tvrdnja "zbir uglova trougla je 137° " je lažno. U suštini, u euklidskoj geometriji, svaka izjava je ili lažna ili istinita, a treća nije data. A početkom dvadesetog veka matematičari su naivno verovali da istu situaciju treba posmatrati u svakom logički doslednom sistemu.

A onda 1931. neki bečki matematičar s naočalama Kurt Gödel- uzeo i objavio kratak članak koji je jednostavno preokrenuo cijeli svijet takozvane "matematičke logike". Nakon dugih i složenih matematičkih i teorijskih preambula, on je doslovno ustanovio sljedeće. Uzmimo bilo koju izjavu poput: "Pretpostavka #247 je logički nedokaziva u ovom sistemu aksioma" i nazovimo je "tvrdnjom A". Dakle, Gödel je jednostavno dokazao sljedeće zadivljujuće svojstvo bilo kojeg sistema 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“. Odnosno, vraćajući se na formulaciju drugog Hilbertovog problema, ako je sistem aksioma potpun (tj. bilo koja izjava u njemu može biti dokazana), onda je nedosljedan.

Jedini izlaz iz ove situacije je prihvatanje nekompletnog sistema aksioma. Odnosno, moramo se pomiriti sa činjenicom da ćemo u kontekstu bilo kojeg logičkog sistema i dalje imati iskaze tipa A koji su očigledno tačni ili lažni, a o njihovoj istinitosti možemo suditi samo izvan okvira aksiomatike koju imamo. usvojeno. Ako takvih tvrdnji nema, onda je naša aksiomatika kontradiktorna, au njenom okviru će se neizbježno naći formulacije koje se mogu i dokazati i opovrgnuti.

Dakle, formulacija Gödelove prve, ili slabe, teoreme o nepotpunosti glasi: "Svaki formalni sistem aksioma sadrži nerazjašnjene pretpostavke". Ali Gedel se tu nije zaustavio, formulišući i dokazujući Gedelovu drugu ili jaku teoremu o nepotpunosti: „Logička potpunost (ili nepotpunost) bilo kojeg sistema aksioma ne može se dokazati u okviru ovog sistema. Da bi se to dokazalo ili opovrglo, potrebni su dodatni aksiomi (jačanje sistema).

Bilo bi sigurnije misliti da su Godelove teoreme apstraktne i da se ne tiču ​​nas, već samo područja uzvišene matematičke logike, ali se u stvari pokazalo da su u direktnoj vezi sa strukturom ljudskog mozga. To je pokazao engleski matematičar i fizičar Roger Penrose (rođen 1931.). Gödelove teoreme može se koristiti za dokazivanje postojanja fundamentalnih razlika između ljudskog mozga i kompjutera. Poenta njegovog rezonovanja je jednostavna. Kompjuter radi strogo logički i nije u stanju da utvrdi da li je izjava A tačna ili netačna ako izlazi iz okvira aksiomatike, a takvi iskazi, prema Gödelovoj teoremi, neizbežno postoje. Osoba, suočena sa tako logički nedokazivom i nepobitnom tvrdnjom A, uvijek je u stanju da utvrdi njenu istinitost ili neistinitost – na osnovu svakodnevnog iskustva. Barem u ovome, ljudski mozak je superiorniji od kompjutera okovanog čistim logičkim sklopovima. Ljudski mozak je u stanju da shvati punu dubinu istine sadržanu u Gedelovim teoremama, ali kompjuter nikada ne može. Stoga je ljudski mozak sve samo ne kompjuter. On je u stanju da donosi odluke i Turingov test će proći.

na temu: "GODELOVA TEOREMA"

Kurt Gödel

Kurt Gödel je najveći specijalista za matematička logika- rođen je 28. aprila 1906. godine u Brunnu (danas Brno, Češka). Diplomirao je na Univerzitetu u Beču, gdje je odbranio doktorsku disertaciju, bio je docent 1933–1938. Nakon anšlusa emigrirao je u Sjedinjene Države. Od 1940. do 1963. Gödel je radio na Princeton institutu visoke studije. Gödel, počasni doktorat sa univerziteta Yale i Harvard, saradnik Nacionalna akademija Nauke Sjedinjenih Država i Američko filozofsko društvo.

Kurt Gödel je 1951. godine dobio najveću naučnu nagradu u Sjedinjenim Državama, Ajnštajnovu nagradu. U članku posvećenom ovom događaju, drugi od najvećih matematičara našeg vremena, John von Neumann, napisao je: „Doprinos Kurta Gödela modernoj logici je zaista monumentalan. Ovo je više od spomenika. Ovo je prekretnica koja razdvaja dvije ere... Bez ikakvog preterivanja se može reći da je Gödelov rad iz temelja promijenio sam predmet logike kao nauke.

Zaista, čak i suhi popis Godelovih dostignuća u matematičkoj logici pokazuje da je njihov autor u suštini postavio temelje za čitave dijelove ove nauke: teoriju modela (1930; tzv. teorema o potpunosti uskog predikatskog računa, koja pokazuje, grubo govoreći, dovoljnost sredstava "formalne logike" da dokaže sve istinite rečenice izražene njenim jezikom), konstruktivnu logiku (1932–1933; rezultira mogućnošću svođenja nekih klasa klasičnih logičkih rečenica na njihove intuicionističke parnjake, koji su temelj za sistematsku upotrebu „operacija uranjanja“ koje omogućavaju takvo smanjenje raznih logičkih sistema jedni druge), formalna aritmetika (1932–1933; rezultati o mogućnosti svođenja klasične aritmetike na intuicionističku aritmetiku, pokazujući u određenom smislu konzistentnost prve u odnosu na drugu), teoriju 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 matematike s jedne strane. A u implementaciji logičkih i matematičkih problema na elektronskim računarima - s druge strane), aksiomatska teorija skupova (1938; dokaz relativne konzistentnosti aksioma izbora i Cantorove hipoteze kontinuuma iz aksioma teorije skupova, što je označilo početak serije ključni rezultati o relativnoj konzistentnosti i nezavisnosti principa teorije skupova).

Godelova teorema o nepotpunosti

Uvod

Godine 1931. u jednom od njemačkih naučni časopisi pojavio se relativno kratak rad s prilično zastrašujućim naslovom "O formalno neodlučivim propozicijama Principia Mathematica i srodnih sistema". Njegov autor je bio dvadesetpetogodišnji matematičar sa Univerziteta u Beču Kurt Gödel, koji je kasnije radio na Princeton Institute for Advanced Study. Ovaj rad je odigrao odlučujuću ulogu u istoriji logike i matematike. U odluci Univerzitet Harvard dodijelivši Gödelu počasni doktorat (1952), opisivana je kao jedna od najveća dostignuća moderna logika.

Međutim, u vrijeme objavljivanja nema naslova Gödelovog djela. Ni njegov sadržaj većini matematičara nije rekao ništa. Pomenuta u svom naslovu, Principia Mathematica je monumentalna trotomna rasprava Alfreda North Whiteheada i Bertranda Russella o matematičkoj logici i osnovama matematike; poznavanje rasprave nikako nije bilo neophodno stanje za uspješan rad u većini grana matematike. Interesovanje za pitanja koja se obrađuju u Gedelovom radu oduvek je bila deo veoma male grupe naučnika. U isto vrijeme, argumenti koje je Gödel dao u svojim dokazima bili su tako neobični za svoje vrijeme. Da je njihovo potpuno razumijevanje zahtijevalo isključivo poznavanje predmeta i poznavanje literature posvećene ovim vrlo specifičnim problemima.

Prva teorema o nepotpunosti

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

Za proizvoljnu konzistentnu formalnu i izračunljivu teoriju u kojoj se osnovne aritmetičke propozicije mogu dokazati, može se konstruisati pravi aritmetički iskaz čija se istina ne može dokazati u okviru teorije. Drugim riječima, bilo koja savršeno korisna teorija dovoljna da predstavi aritmetiku ne može biti i konzistentna i potpuna.

Ovdje riječ "teorija" znači " beskonačan skup» izjave, od kojih se za neke pretpostavlja da su istinite bez dokaza (takve tvrdnje se nazivaju aksiomi), dok se druge (teoreme) mogu izvesti iz aksioma, pa se stoga pretpostavlja (dokazuje) da su istinite. Izraz "dokazivo u teoriji" znači "izvedeno iz aksioma i primitiva teorije (konstantni simboli abecede) korištenjem standardne (prvog reda) logike." Teorija je konzistentna (konzistentna) ako je u njoj nemoguće dokazati kontradiktornu tvrdnju. Izraz “može se izgraditi” znači da postoji neka mehanička procedura (algoritam) koja može izgraditi iskaz zasnovan na aksiomima, primitivima i logici prvog reda. "Elementarna aritmetika" je prisustvo operacija sabiranja i množenja nad prirodnim brojevima. Rezultirajuća istinita, ali nedokaziva tvrdnja se za datu teoriju često naziva "Gödelov niz", ali postoji beskonačan broj drugih tvrdnji u teoriji koje imaju isto svojstvo da su nedokazivi unutar teorije.

Pretpostavka da je teorija izračunljiva znači da je u principu moguće implementirati kompjuterski algoritam ( kompjuterski program) koji (ako mu je dozvoljeno da izračuna proizvoljno duga vremena, do beskonačnosti) izračunava listu svih teorema teorije. U stvari, dovoljno je izračunati samo listu aksioma, a sve teoreme se mogu efikasno izvesti iz takve liste.

Prva teorema o nepotpunosti nazvana je "Teorem VI" u Gödelovom radu iz 1931. godine. O formalno neodlučivim propozicijama u Principia Mathematica i srodnim sistemima I. U originalnom Gödelovom snimku zvučalo je ovako:

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

Teorema VI .

Za svaku ω-konzistentnu rekurzivnu klasu k FORMULA postoje rekurzivni ZNAKOVI r tako da ni jedno ni drugo (v Gen r), niti ¬( v Gen r)ne pripadaju Flg (k)(gdje je v FREE VARIABLE 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 može se dokazati unutar teorije, onda bi teorija sadržavala teoremu koja je kontradiktorna sama sebi, i stoga bi teorija bila nekonzistentna. Ali ako G nedokazivo, onda je istinito i stoga je teorija nekompletna (tvrdnja G ne može se zaključiti u njemu).

Ovo objašnjenje je uobičajeno prirodni jezik, pa stoga nije baš matematički rigorozan. Da bi pružio rigorozan dokaz, Gödel je numerisao izjave sa prirodni brojevi. U ovom slučaju, teorija koja opisuje brojeve takođe pripada skupu propozicija. Pitanja o dokazivosti tvrdnji 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 sa nekim određenim svojstvom. Broj sa ovim svojstvom će biti dokaz nekonzistentnosti teorije. Ako takav broj postoji, teorija je nedosljedna, suprotno prvobitnoj pretpostavci. Dakle, pod pretpostavkom da je teorija konzistentna (kao što sugerira premisa teoreme), ispada da takav broj ne postoji, a Gödelova izjava je tačna, ali to se ne može dokazati u okviru teorije (dakle, teorija je nepotpuna) . Važna konceptualna napomena je da se mora pretpostaviti da je teorija konzistentna da bi se Gedelova izjava proglasila istinitom.

Druga Gödelova teorema o nepotpunosti

Gödelova druga teorema o nepotpunosti glasi kako slijedi:

Za bilo koju formalno rekurzivno nabrojivu (tj. efikasno generiranu) teoriju T, uključujući osnovne izjave aritmetičke istine i određene formalne izjave dokazivosti, ovu teoriju T uključuje izjavu o svojoj konzistentnosti ako i samo ako je teorija T nekonzistentna.

Drugim rečima, dovoljna je doslednost bogata teorija ne može se dokazati pomoću ove teorije. Međutim, može se ispostaviti da se konzistentnost jedne određene teorije može uspostaviti pomoću druge, snažnije formalne teorije. Ali onda se postavlja pitanje konzistentnosti ove druge teorije i tako dalje.

Mnogi su pokušali da koriste ovu teoremu da dokažu da se inteligentna aktivnost ne može svesti na proračune. Na primjer, davne 1961. godine poznati logičar John Lucas smislio je sličan program. Pokazalo se da je njegovo razmišljanje prilično ranjivo - međutim, zadatak je postavio šire. Roger Penrose ima malo drugačiji pristup, koji je u knjizi predstavljen u potpunosti, "od nule".

Diskusije

Posljedice teorema utječu na filozofiju matematike, posebno na one formalizme koji se koriste formalna logika da definišu svoje principe. Prvi teorem o nepotpunosti može se preformulisati na sljedeći način: nemoguće je pronaći sveobuhvatan sistem aksioma koji bi se mogao dokazati sve matematičke istine, a nijedna laž". S druge strane, sa stanovišta stroge formalnosti, ova reformulacija nema mnogo smisla, jer pretpostavlja da se koncepti „istina“ i „laž“ definišu u apsolutnom smislu, a ne u relativnom smislu. svaki konkretan sistem.