uvod.tex

\chapter[]{Predgovor}

%\section{Neka vrst predgovora}

Već nekoliko godina na Matematičkom odsjeku Prirodoslovno-matematičkog fakulteta u Zagrebu držim kolegij Izračunljivost --- izvorno uveden kao prirodni nastavak kolegija Matematička logika (čijim je dijelom dugo bio), s ciljem dokaza Churchova teorema o neodlučivosti logike prvog reda. Tako je nastala knjiga~\cite{skr:Vuk}, izdvajanjem iz knjige~\cite{skr:VukML}, prvenstveno namijenjene studentima teorijske matematike koji žele produbiti svoje znanje o matematičkoj logici.

U međuvremenu, zbog raznih okolnosti, kolegij su počeli upisivati mahom studenti računarstva, kojima je pojam algoritma daleko općenitiji i intuitivno bliži od onog potrebnog za dokaz Churchova teorema. U suvremenom svijetu okruženi smo računalima raznih vrsta, često ih programiramo da bismo ih prilagodili svojim potrebama, i algoritamske sustave više ne doživljavamo kao nešto apstraktno. Pojam izračunljive funkcije (implementirane u nekom programskom jeziku) počeo je već u umovima studenata računarstva istiskivati skupovnoteorijsku ideju uređene trojke $(\text{domena},\text{kodomena},\text{graf}\mspace{2mu})$ kao asocijaciju na pojam "funkcija". Rekurzija više nije egzotična matematička konstrukcija, već sasvim uobičajen alat u repertoaru gotovo svakog programera. Jezici više nisu reprezentirani črčkarijama na papiru ili otiscima na traci (kao u Turingovo vrijeme), već tekstnim datotekama, nizovima bajtova u određenom \emph{encodingu}, koji se sasvim prirodno obrađuju programskim alatima. Strukture više nisu dijagrami matematičkih simbola povezanih strelicama, nego memorijski blokovi objekata povezanih pokazivačima ili referencama. \emph{Halting problem} nije više nešto maglovito i daleko od svakodnevnog iskustva: svi smo doživjeli da se računalo privremeno smrzne, i bili u nedoumici koliko dugo čekati prije nego što dobijemo nekakav odziv\!, ili zaključimo da se permanentno smrznulo i ne preostaje nam drugo doli posegnuti za gumbom za ponovo pokretanje. 

U tom svjetlu, počeli su se pokazivati određeni nedostaci knjige~\cite{skr:Vuk}. Zahvaljujući njenom nastojanju da izgradi matematičku intuiciju --- zanemarujući ili čak namjerno potiskujući intuiciju koju računarci već imaju o tim pojmovima --- konačni učinak za većinu studenata bio je vrlo sličan onom koji je primijetio Eric Mazur~\cite{mazur} u svojoj nastavi fizike:
\begin{quote}
    \emph{Professor, how should I answer these questions: according to what you \\ taught me, or according to the way I usually think about these things?}
\end{quote}

Nažalost, znao sam i ja dobivati takva pitanja --- ili sam uočio da studenti pri programiranju koriste jedan mentalni model, a pri rješavanju zadataka sasvim drugačiji. I pritom naravno čine bitno više početničkih pogrešaka --- jer taj drugi model izgrađuju tek nekoliko mjeseci, dok prvi izgrađuju desetak godina.

Knjiga koju čitate pokušaj je ispravljanja tog dojma. \textbf{Ne postoje dva svijeta}, svijet modernog računarstva i svijet klasične teorije izračunljivosti. To je jedan te isti svijet, samo što je u matematičkom modelu pojednostavljen (slično kao i model njutnovske mehanike: vakuum, linearno trenje, materijalne točke,~\ldots) --- ali svi bitni pojmovi teorijskog računarstva se u njemu mogu modelirati, svaka intuicija se može validirati, i svaki fenomen se može uočiti. Ako ste "računarac u duši", sve potrebne ideje već imate. I najvažnije, sistematizacija i razumijevanje koje iz toga proizlaze su nezamjenjivi.

Što ako \emph{niste} računarac u duši? Knjiga~\cite{skr:Vuk} je fantastična za izgradnju matematičke intuicije. Praktički jedini njen nedostatak je invalidacija računarske intuicije --- ako tu intuiciju nemate, nedostatka nema. Trudio sam se održati kompatibilnost, tako da čak možete neke pojmove naučiti otamo, a neke odavdje.

%\section{O knjizi}

Iako je knjigu sasvim moguće isprintati na papir i šarati po njoj, prvenstveno je namijenjena digitalnom čitanju. Zato ima mnogo referenci (označenih posebnom bojom), na svaku od kojih je moguće kliknuti da bi se vidjelo na što se odnosi. Ako koristite "pravi" PDF-čitač (za razliku od ovih što dođu s \emph{browserima}), možete se i vratiti tipkom \keys{$\Mapsfrom$}, ili kombinacijom $\text{\keys{Alt}}(+\text{\keys{Shift}})+\text{\keys{$\leftarrow$}}$. Pravi čitač omogućuje vam i navigaciju kroz naslove, bolji \emph{rendering}, označavanje omiljenih stranica i još neke stvari zbog kojih ga se isplati instalirati. Moja preporuka je \textsf{SumatraPDF} na Windowsima, \textsf{Okular} na Linuxu te \textsf{Document Viewer} na Androidu. Ako imate dovoljno RAM-a, \textsf{Adobe Reader} je također opcija. Ako baš morate čitati u internetskom pregledniku, čujem da \textsf{Firefox} ima relativno dobar \emph{plugin}.

Knjiga je pisana u \textsf{\LaTeX{}}u, klasa \textsf{KOMA-Script book}, koristeći internetsku uslugu \emph{Overleaf} koja je vjerojatno najbolji besplatni način za produkciju visoko zahtjevnih dokumenata "u oblaku". Font je Knuthov Concrete iz serije \emph{Concrete Mathematics}, a za matematiku Zapfov \AmS{} $Euler$ i $\mathsf{MnSymbol}$. Ako vas zanima išta detaljnije o produkciji knjige, možete mi pisati na \href{mailto:veky@math.hr}{veky@math.hr}, ili pogledati u (ne sasvim ažuran) repozitorij na \href{https://github.com/vedgar/izr}{github.com/vedgar/izr}. Ako uočite bilo kakvu grešku u knjizi, ili smatrate da bi nešto trebalo drugačije prezentirati, pošaljite \emph{email} ili \emph{pull request}.

Duljina knjige prvenstveno je posljedica moje želje da gotovo sve dokaze raspišem do sitnih detalja, kako bih sebi i vama pokazao da ništa nije provučeno "ispod stola" te da biste uočili da osnovnih ideja zapravo nema puno. Ogroman broj dokaza provodi se matematičkom indukcijom, rastavom na slučajeve, ili pak eksplicitnom konstrukcijom (\emph{programiranjem}) objekata koji zadovoljavaju traženu specifikaciju. Ako vam se bilo koji dokaz učini prelaganim (ili preteškim), ne morate ga čitati, ali tako se izlažete riziku da propustite uočiti sličnu ideju u nekom idućem dokazu. Drugi uzrok veličine knjige je velik broj primjera. Vjerojatno najčešći prijedlog studenata za poboljšanje nastave na evaluacijskim anketama bio je da stavim više primjera. Čuo sam vas, i nadam se da je ovo dovoljno --- ako nije, recite.

Ime ove knjige --- \emph{Komputonomikon} --- relativno je doslovni prijevod njene svrhe: prikaz ({\textgreekfont\textepsilon\textiota\textkappa\'o\textnu\textalpha}) zakona ({\textgreekfont\textnu\'o\textmugreek\textomikron\textvarsigma}) računanja (\textsc{compvtvs}). Kombiniranje grčkih i latinskih korijena omiljena je razonoda računaraca: promotrite primjer pridjeva "heksadecimalan".

Sastavni dio ove knjige je i \emph{Komputrivij}, zbirka u kojoj se nalaze brojni zadaci: od šablonskih za vježbu, preko svih zadataka sa starih kolokvija i pismenih ispita do kojih sam uspio doći (zahvaljujem bivšim asistentima iz Izračunljivosti, Zvonku Iljazoviću i Marku Doki, na ustupanju zadataka), do zadataka koji na određeni način nadopunjuju teoriju izloženu u ovoj knjizi, ali nisu nužni za njeno razumijevanje.

Zahvalan sam kolegama i studentima koji su čitali rane \emph{draftove} ove knjige, i brojnim prijedlozima pridonijeli njenom poboljšanju. Među njima bih svakako istaknuo Marka Horvata, koji još uvijek nije uvjeren da je računarac, ali je pristao igrati tu ulogu za potrebe čitanja Komputonomikona.

\section[]{Motivacija}

Izračunljivost: matematička obrada pojma algoritma. Čemu to služi? Zar ne znamo pisati algoritme i bez matematičke formalizacije? Koga je zapravo briga za definicije poput "Algoritam je uređena sedmorka skupova~\ldots", i beskorisne propozicije poput "Postoji algoritam za sortiranje liste cijelih brojeva"? Dva su odgovora: praktični i teorijski.

Kažemo da znamo pisati algoritme. Ali kako to činimo? Zapravo ih najčešće \emph{implementiramo} u nekom programskom jeziku, prešutno podrazumijevajući da je ono što taj jezik omogućava izraziti ni više ni manje nego algoritam. S tim shvaćanjem postoje dva problema.

Prvo, programski jezici nastaju godišnjim ritmom, a jezik koji postane toliko popularan da se u njemu počnu pisati općeniti algoritmi, nastane možda svakih desetak godina. Zatrpani smo knjigama koje objašnjavaju besmrtne algoritamske koncepte, pokušavajući nam ih "približiti" implementirajući ih u odavno mrtvom jeziku. Neke od tih knjiga~\cite{sedgewick} su toliko popularne da su autori gotovo primorani pisati nova izdanja, u kojima su algoritmi potpuno isti, ali je programski jezik promijenjen. Tu se krije implicitna pretpostavka da, što god jedan programski jezik može izraziti, može i drugi. No kako možemo biti sigurni u to? Na primjer, originalni FORTRAN nije dopuštao rekurziju, dok ALGOL jest~\cite{url:recursionAlgol}. Može li se svaki rekurzivni algoritam zapisati nerekurzivno? Možemo li to dokazati? Također, ako implicitno vjerujemo da su svi programski jezici ekvivalentni, zašto cijelo vrijeme stvaramo nove? Razuman odgovor je da se razlikuju u \emph{nečem drugom}, ne u algoritmima koje prezentiraju. Možemo li to \emph{drugo} eliminirati, svodeći algoritme na "čistu esenciju"?

Drugi problem sastoji se u tome da programski jezici nastaju s raznim svrhama, ali izuzetno rijetko s primarnom svrhom vjerne reprezentacije matematičkih objekata --- a još rjeđe takvi jezici postanu planetarno popularni. Popularni jezici su obično opterećeni performansama: optimalnom upotrebom procesora (vremena) i memorije (prostora), i kao posljedica toga njihov dizajn čini hardveru razne ustupke, koji se teško mogu matematički opravdati. Izuzetno je česta pojava, na primjer, da cijele brojeve računala ne reprezentiraju kao elemente prstena $\mathbb Z$, već prstena $\mathbb Z\big\slash2^{64}\mathbb Z$. Tako nastaje raskorak između algoritma i implementacije, koji ima važne praktične posljedice~\cite{url:wrongBinsearch}. Također, često se instrukcije ne izvršavaju redom kojim se nalaze u izvornom kodu, u svrhu bržeg izvršavanja na višejezgrenim procesorima --- ponekad je čak sam pojam redoslijeda izvršavanja besmislen~\cite[str.\ 10]{art:memorymodels}.

Teorijski odgovor na motivacijsko pitanje dobijemo kad se zapitamo što, u općenitom smislu, matematičare navede na formalizaciju nekog pojma. Ponekad je to otkriće paradoksa, ali češće se radi o potrebi da se dokaže \emph{nepostojanje} objekta neke klase $\mathcal K$ s nekim svojstvima. Iako smo se za dokaze postojanja mogli osloniti na intuitivni osjećaj da objekte klase $\mathcal K$ "prepoznamo kad ih vidimo", to nam više nije dovoljno ako slutimo da traženi objekt ne postoji i želimo to dokazati. A u svakom se području s vremenom pojave problemi koji odolijevaju svim poznatim metodama, i počne se sumnjati da su možda nerješivi.

Dok nitko nije dovodio u pitanje Euklidove konstrukcije, daleko preciznija formulacija geometrijske konstruktibilnosti bila je potrebna da se dokaže da je trisekcija kuta ravnalom i šestarom nemoguća. Dok je za pronalazak Cardanove ili Ferrarijeve formule bilo dovoljno znati nekoliko algebarskih manipulacija, tek je Galoisova teorija omogućila dokaz da analogni postupci nisu mogući za algebarske jednadžbe petog i višeg stupnja. Dok je već Galileo vidio da prirodnih brojeva i njihovih kvadrata ima jednako mnogo koristeći intuitivni pojam bijekcije, bitno je stroža formulacija bila potrebna Cantoru za dijagonalni argument kojim je dokazao da bijekcija između $\N$ i $\mathbb R$ ne postoji. Na meta-razini također: Cantor je uspio naći dokaze za mnoge tvrdnje ili njihove negacije u svojoj teoriji skupova, ali tek je formalna aksiomatizacija omogućila da se dokaže da se takvi dokazi za neke tvrdnje (kao što je hipoteza kontinuuma), niti za njihove negacije, ne mogu naći jer ne postoje.

Od davnina je poznat problem rješavanja \emph{diofantskih jednadžbi} --- nalaženja prirodnih brojeva koji zajedno s još nekim fiksnim prirodnim brojevima, zbrajanjem i množenjem, čine dva izraza jednakima. Modernim jezikom, zadan je polinom s cjelobrojnim koeficijentima u $k$ varijabli (recimo, $x_2^3-x_1^2-1$), i želimo ustanoviti ima li nultočku u $\N^k$ --- ili u $\mathbb Z^k$, što se može svesti na prirodni slučaj. Za mnoge specijalne polinome znali smo odgovor, za mnoge specijalne potklase (na primjer, kad je broj varijabli~$k$, ili stupanj polinoma, jednak $1$) poznavali smo od davnina algoritme za nalaženje nultočaka, ali opći algoritam, koji bi za svaki takav polinom u konačno mnogo koraka odgovarao na pitanje ima li prirodnu nultočku, nismo imali. Na slavnom Hilbertovu popisu 23 velika matematička problema, deseti je pronalazak takvog algoritma. Protokom vremena, iskristalizirala se mogućnost da algoritam ne postoji, ali za pravi dokaz toga trebalo je prvo formalizirati pojam algoritma. Nakon što je to učinjeno, relativno brzo (uzevši u obzir da su diofantske jednadžbe bile poznate tisućama godina) je Jurij Vladimirovič Matijasevič riješio deseti Hilbertov problem --- očekivano, dokazom nepostojanja takvog algoritma.

Nije to bio jedini takav problem: nađeni su brojni drugi problemi za koje se sličnim metodama dokazalo da su algoritamski nerješivi. Danas znamo da je neizračunljivost "posvuda", i nismo njome više toliko fascinirani, ali to je samo znak ogromnog puta koji smo prešli u shvaćanju algoritama tijekom dvadesetog stoljeća. Jedan dio tog puta prikazan je u ovoj knjizi.

%\section{Opća i univerzalna izračunljivost}
\section[]{Predmet proučavanja}

Cilj teorije izračunljivosti je pokazati da pojam izračunljive funkcije zapravo ne ovisi o podlozi na kojoj se njen algoritam izvršava. Iako je lako naći prejednostavne sustave (kao što su na primjer konačni automati, koji ne mogu čak niti uspoređivati proizvoljno velike prirodne brojeve), nakon neke točke dovoljne kompleksnosti svi mehanički sustavi postaju \emph{ekvivalentni} po pitanju toga koje funkcije, uz razumno kodiranje njihovih ulaza i izlaza, računaju. To se vidi iz činjenice da je svaki od njih sposoban \emph{simulirati} sve druge: reprezentirati njihove konfiguracije (ili njihove kodove) unutar svojih, i izvršavati korake njihova računanja kao (možda komplicirane) procedure na svojim konfiguracijama. Suvremeno računarstvo poznaje taj fenomen pod imenom "virtualizacija". \emph{Church--\!Turingova teza} ide i dalje: kaže da se ne samo svi algoritmi izvršivi na svim formalnim modelima izračunljivosti, već i svi "intuitivno zamislivi" algoritmi, mogu izvršavati na nekom konkretnom modelu izračunljivosti, primjerice na Turingovu stroju. Tu tezu nije moguće formalno dokazati sve dok se ne dogovorimo oko općih aksioma izračunljivosti~\cite{dershowitz}, ali svaki dokaz ekvivalencije sustava izračunljivosti pruža dodatnu empirijsku potvrdu za nju.

Drugim riječima, izračunljivost je \emph{opći} fenomen: u kojem god modelu da je definiramo, ona će obuhvatiti iste funkcije --- ili barem iste s obzirom na prirodno kodiranje ulaza i izlaza. Na primjer, algoritmi za zbrajanje dekadski zapisanih i binarno zapisanih prirodnih brojeva su različiti, ali oba su zapravo samo reprezentacije brojevne funkcije $\f{add}^2$, s obzirom na različite zapise (dekadski odnosno binarni) samih prirodnih brojeva.

Također, jedan od tih modela --- pa onda i svi ostali, simulacijom --- je \emph{univerzalan}: ne samo da svaka izračunljiva funkcija ima algoritam unutar tog modela, nego možemo naći \emph{jedan} algoritam koji (ovisno o ulazima) može računati \emph{sve} izračunljive funkcije, odnosno simulirati sve algoritme. Granica "dovoljne kompleksnosti" na kojoj se postiže opća izračunljivost i univerzalnost, za neke modele je začuđujuće nisko. Promotrit ćemo tri vrste takvih sustava: Turingove i RAM-strojeve te parcijalno rekurzivne funkcije.

\section[]{Pregled po poglavljima}
Slijedi okvirni prikaz rezultata obrađenih u pojedinim poglavljima knjige. Za više detalja pogledajte sadržaj.

U prvom poglavlju uvodimo brojevni model izračunavanja (računanje funkcija koje rade s prirodnim brojevima), kroz imperativno programiranje --- RAM-strojeve i makro-strojeve u stilu Shoenfielda~\cite{shoenfield}. Opisujemo tehniku spljoštenja (\emph{inlining}) kojom se svaki makro-program može pretvoriti u ekvivalentni RAM-program.

U drugom poglavlju dajemo alternativni brojevni model, kroz funkcijsko programiranje --- rekurzivne funkcije u stilu Kleeneja. Koristeći funkcijski makro i spljoštenje, konstruiramo kompajler parcijalno rekurzivnih funkcija u RAM-programe, pokazujući da imperativna paradigma može simulirati funkcijsku (računajući iste funkcije).

U trećem poglavlju uvodimo kodiranje, pomoću kojeg možemo u brojevnom modelu računati i funkcije na objektima koji nisu prirodni brojevi. Koristeći kodiranje, konstruiramo interpreter RAM-programa u funkcijskom jeziku, pokazujući ekvivalentnost imperativne i funkcijske paradigme (Kleenejev teorem o normalnoj formi).

U četvrtom poglavlju uvodimo jezični model izračunavanja (računanje funkcija koje rade s nizovima znakova), kroz Turingove strojeve u stilu Sipsera~\cite{sipser}. Opisujemo Turing-izračunavanje parcijalno rekurzivnim funkcijama i transpiliramo RAM-strojeve u Turingove strojeve, čime dokazujemo ekvivalentnost brojevne i jezične izračunljivosti.

U petom poglavlju generaliziramo dobivene rezultate ekvivalentnosti raznih modela izračunavanja kroz Church--\!Turingovu tezu te napokon dokazujemo rezultate o nepostojanju algoritma za pojedine probleme, kao što je Churchov teorem o neodlučivosti logike prvog reda. Skiciramo kako se iz toga može dobiti G\"odelov prvi teorem nepotpunosti.

U šestom poglavlju dokazujemo četiri velika teorema o metaprogramiranju: teorem o parametru (posebni slučaj spljoštenja), teorem rekurzije (rješavanje općih rekurzija), teorem o fiksnoj točki (izračunljiva transformacija RAM-programa ne mijenja semantiku nekoga od njih) i Riceov teorem (semantička svojstva RAM-programa nisu odlučiva).

U sedmom poglavlju uvodimo rekurzivnu prebrojivost kao formalizaciju poluodlučivosti te je karakteriziramo na razne načine kako u brojevnom tako i u jezičnom modelu: kao projekcije rekurzivnih relacija, kao čekanje na zaustavljanje izračunavanja, kao enumeracije (slike rekurzivnih nizova) i kao grafove parcijalno rekurzivnih funkcija.