Uticaj matematike na nastanak i temelje računarstva (2. deo)
Autor: Nedeljko Stefanović
Gedelovi i Tjuringovi rezultati
Još je Euklid shvatio da se ne mogu svi stavovi dokazati, već da se mora poći od nekih početnih stavova iz kojih se izvode ostali. Od njega potiče aksiomatski metod. Kasnije je uočeno da isto važi i za pojmove. Ne mogu se svi definisati, već se od nekih mora poći (osim ako prihvatimo induktivno uvođenje pojmova preko primera i kontraprimera, što ima prednosti i mane, a koje u zasnivanju matematike nije prihvaćeno). Aksiomatski metod se razvijao, a nemački logičar Gotlob Frege (1848-1925) uočio je da i samu logiku na koju se oslanjaju aksiomatske teorije treba nekako opisati.
Formalna teorija se sastoji najpre od nekog izabranog skupa simbola, zatim od skupa formula, koje su ništa drugo do neki izabrani konačni nizovi simbola, zatim od aksioma, koje su, takođe, neke od izabranih formula i od nekih izabranih pravila izvođenja, po kojima se od nekih formula dobija neka druga formula. Teoreme su onda formule koje se mogu dobiti polazeći od aksioma konačnom primenom pravila izvođenja.
Ovakav pristup, koji ne zahteva udubljivanje u značenje aksioma, formula i pravila, omogućava da računari, koji ne mogu da se udube u sadržaj, već samo rade po strogo definisanom skupu mehaničkih pravila, mogu da se primenjuju na složene matematičke teorije.
Međutim, treba naglasiti da time matematika nije šablonizovana. Takvi sistemi se mogu uporediti sa šahovskom igrom. Ona je definisana jednostavnim pravilima igre, čije poznavanje omogućava proveru da li je tok partije ispravan i koji je konačan ishod igre, ali ne obezbeđuju uspeh u igranju šaha, već je za to potrebna i veština vođenja šahovskih figura. Tako je za formalne teorije moguće napisati program koji proverava ispravnost dokaza teorema u toj teoriji, ali je problem pronalaženja dokaza teorema daleko složeniji.
Osim toga, nameće se pitanje moći tog pristupa. Sa jedne strane, svaka teorija ima svoj jezik, a svaki jezik ima ograničenu izražajnu moć, tj. na njemu nije moguće izraziti bilo šta. Samim tim, od teorije se ne može očekivati da odgovori na bilo kakva pitanja, već samo na ona koja se mogu postaviti na njenom jeziku. Onda se nameće pitanje da li teorija može da odgovori na sva takva pitanja. Za takve teorije se kaže da su potpune.
Gedelovi rezultati
Austrijsko-američki matematičar (logičar) Kurt Gedel (1906-1978) bavio se upravo ovim pitanjima. Dokazao je da se matematika ne može formalizovati na neprotivrečan način tako da taj formalizam može da da odgovor na svako pitanje koje se u okviru njega može postaviti. Međutim, ovaj iskaz u navedenoj formulaciji zapravo nije tačan. Elementarno je logičko tvrđenje da se svaki neprotivrečan formalan sistem može dopuniti do neprotivrečnog i potpunog formalnog sistema.
Stoga je Gedel uveo još jedan uslov – da su aksiome i pravila algoritamski opisivi. To zapravo znači da imamo potpuno definisan postupak na osnovu koga znamo da li je neka formula aksioma i da li je neka formula neposredno izvodiva iz nekih drugih formula po nekom od pravila izvođenja. Taj uslov je prirodan, jer u suprotnom nema previše smisla sistem smatrati formalnim. To je ujedno današnji stepen razvoja u zasnivanju matematike i mada nemamo potpune formalizacije matematike, postoji formalizacija koja predstavlja osnovne matematičke principe prihvaćene od strane najvećeg broja matematičara.
No, pošto je to sastavni deo formulacije i dokaza, bilo je neophodno da se sam pojam algoritma opiše matematički, tj. formalno, a Gedelov tzv. sistem rekurzivnih funkcija jeste prvo svođenje pojma algoritma na konačan broj jednostavnih pravila.
Tjuringovi rezultati
Taj sistem, međutim, nije bio podesan za realizaciju u vidu mašine. Mada bi načelno to bilo moguće, takva bi mašina bila mnogo složenija, nego što je neophodno, jer Gedel to nije imao u vidu budući da je taj sistem osmislio za sasvim drugu svrhu. Nakon objave Gedelovog rada „O formalno neodlučivim iskazima principa matematike i srodnih sistema” (1931), Gedel je (1934) držao predavanja na seminaru na Univerzitetu u Prinstonu. Predavanja su kulminirala objavljivanjem naučnih radova drugih istraživača, od kojih je za nastanak računara najznačajniji rad britanskog matematičara Alana Tjuringa „O izračunljivim brojevima sa primenom na problem odlučivosti” (1936), u kome je Tjuring dao potpuno drugačije zasnovan, ekvivalentan opis algoritma, koji je sadržao i opis jednostavne mašine koja po tom opisu algoritma može da radi. Štaviše, algoritam je opisan upravo opisom takve mašine.
Nažalost, ubrzo je izbio Drugi svetski rat, a ova otkrića su primenjena na razbijanje nemačke vojne šifre „enigma”. Mašinsko šifrovanje je inače postojalo i u Prvom svetskom ratu, ali nije bilo mogućnosti da se takva mašina napravi, jer su nedostajala ova otkrića. No, da do Drugog svetskog rata nije došlo, računari bi se svakako koristili u neke humanije svrhe jer se do potrebnih otkrića već došlo, tako da tom ratu nemamo na čemu da se zahvalimo (prim.aut.).
Tu se odmah nameće pitanje kako znamo da su time obuhvaćeni svi algoritmi. Takozvana Čerč-Tjuringova teza tvrdi da se ovako uveden pojam algoritma poklapa sa intuitivnim shvatanjem algoritma, ali pošto učestvuje jedan nematematički pojam, ona nije matematičko tvrđenje, pa se ne može dokazati matematičkim sredstvima.
No, to ne znači da ne možemo reći ništa o tom pitanju. Prvo, smatra se da pošto postoje suštinski različiti pristupi opisu pojma algoritma, svi oni dovode do istog skupa algoritama (ekvivalentnost poznatih sistema izračunljivosti je matematička teorema), što predstavlja jednu empirijsku potvrdu Čerč-Tjuringove teze. Naravno, takav argument nije matematički, inače bi Čerč-Tjuringova teza bila teorema.
Takođe, ti sistemi izračunljivosti pokrivaju sve numeričke algoritme potrebne za rešavanje jednačina postojećih fizičkih teorija. Stoga, da bismo napravili pouzdanu mašinu, koja rešava neki deterministički zadatak sa jednoznačnim rezultatom (čemu služe algoritmi u svojoj osnovnoj formulaciji), bilo bi neophodno otkriti neke do sada nepoznate prirodne pojave koje se ne mogu opisati zakonima, a koji se mogu numerički rešavati algoritmima obuhvaćenim postojećim opisima pojma algoritma.
Postojanje verovatnosnih fizičkih teorija ne menja ništa, jer se za pouzdane mašine može na osnovu početnog stanja numerički odrediti najverovatnije završno stanje. Ipak, ova argumentacija se može primeniti samo na veštačke mašine, koje su napravljene svesno na osnovu trenutnog znanja konačne složenosti, a ne i na ljudski mozak, koji je nastao spontano evolucijom, na osnovu prirodnih zakona koji nisu u potpunosti proučeni i za koje se ne zna kakav im je stvaran oblik i kolika im je stvarna složenost (prim.aut.). Naučne teorije su samo trenutno ljudsko razumevanje prirode, koja se njima opisuje samo približno i delimično, a napredak nauke se sastoji u tome što one vremenom postaju sve tačnije i sve potpunije.