ram.tex

\chapter{RAM-izračunljivost}

\section{Pojam izračunljive funkcije}

Da bismo odgovorili na pitanje što je algoritam, zapitajmo se za početak što algoritam \emph{radi}  --- ili, što mi algoritmom radimo. Algoritam možemo \emph{pokrenuti} na nekim \emph{ulaznim podacima}, izvršavati njegove \emph{korake} preciznim \emph{redom} te, u nekom trenutku kad algoritam to zatraži, \emph{zaustaviti} postupak i dobiti \emph{izlazne podatke}. Algoritam, u tom pogledu, obavlja nekakvu \emph{transformaciju} podataka. Štoviše, algoritam bi trebao biti \emph{determinističan}: isti ulazni podaci trebali bi proizvesti iste izlazne podatke. Matematička formalizacija te transformacije je pojam \emph{funkcije}: algoritam \emph{preslikava} ulazne podatke u izlazne. Kažemo da algoritam \emph{računa} funkciju, i takve funkcije (za koje imamo algoritme) zovemo \emph{izračunljivima}. Tako pitanje "Kakvi su algoritmi mogući?" postaje nešto preciznije pitanje "Koje su funkcije izračunljive?".

% \subsection{Vrste i količina podataka}

Da bismo funkciju mogli matematički zapisati, moramo precizirati domenu i kodomenu. \emph{Što} su naši podaci?
Na prvi pogled, mogu biti bilo što: imamo algoritme koji rade na cijelim brojevima, realnim brojevima (preciznije, njihovim aproksimacijama --- vidjet ćemo zašto je to bitno), tekstnim podacima (\emph{strings}), datotekama, mrežnim vezama (\emph{sockets}), drugim algoritmima (\emph{higher order programming}), grafovima, objektima, regularnim izrazima, i tko zna čemu. No iskustvo programiranja nas uči da se svi ti raznorazni \emph{tipovi} podataka uvijek mogu --- i moraju, ako želimo nešto raditi s njima --- reprezentirati u memoriji računala kao neki binarni podaci: konačni nizovi nula i jedinica.

Dakle, mogli bismo uzeti $\{0,1\}^*:=\bigcup_{k\in\mathbb N}\,\{0,1\}^k\nomenclature{$S^*$}{skup konačnih nizova elemenata iz $S$}$ kao univerzalni skup naših podataka --- ali pokazuje se da je zgodnije ako umjesto $\{0,1\}$ uzmemo proizvoljni konačni neprazni skup ("abecedu") $\Sigma$. Funkcije iz $\Sigma^*$ u $\Sigma^*$ zovemo \emph{jezične funkcije}, i to je povijesno bio prvi pokušaj formalizacije algoritma: Turingov stroj, kojim ćemo se baviti u poglavlju~\ref{ch:Turing}.

Ipak, skup $\{0,1\}^*$, kao i općeniti $\Sigma^*$, matematički je nespretan; recimo, ako hoćemo nešto o njemu dokazati indukcijom, moramo u koraku posebno razmatrati dodavanje nule, a posebno dodavanje jedinice. Ako hoćemo napraviti neku petlju kroz njega, nije baš lako odrediti sljedbenik zadanog elementa. Nezgoda je i u tome što uobičajenim leksikografskim uređajem nije dobro uređen: na primjer, skup $\{0^n1\mid n\in\N\}$ nema najmanji element.

Za dokazivanje teorema bolje je uzeti jednostavniji skup --- u najvećem dijelu knjige promatrat ćemo \emph{brojevne} algoritme, kojima su ulazni i izlazni podaci \textbf{prirodni brojevi}. U nekom smislu, skup prirodnih brojeva je najjednostavniji mogući skup na kojem se može obrađivati teorija izračunljivosti --- svakako je najjednostavniji među beskonačnim skupovima, a izračunljivost na konačnim skupovima je trivijalna: algoritam za svaku funkciju se može napisati kao tablica (\emph{lookup table}).

Odabir skupa $\N$ kao osnovnog isplatit će se kroz jednostavnost mnogih dokaza (jer imamo matematičku indukciju, jasan početak i sljedbenik, dobar uređaj,~\ldots), ali s druge strane, zato će biti kompliciranije \emph{kodirati} razne druge matematičke objekte kao prirodne brojeve. Za usporedbu, skup $\Sigma^*$ je zgodniji za kodiranje, jer već imamo intuitivnu predodžbu zapisivanja raznih objekata nizanjem znakova ($\Sigma=$ ASCII\@): nitko nam ne mora objasniti kodiranje da bismo znali koji element od $\mathbb Q$ predstavlja \emph{string} "\t{-22/3}".

Ipak, neintuitivnost kodiranja nadomjestit će jednostavnost algoritama: dok je, uz odgovarajuće tehnike~\cite{posav}, lako napisati algoritam za npr.\ zbrajanje racionalnih brojeva kodiranih prirodnim brojevima, analogni algoritam za ASCII-kodirane razlomke gotovo nikada ne stigne dalje od grubog pseudokoda. Ponegdje, gdje su naši objekti već \emph{definirani} kao nizovi znakova (najvažniji primjer su formule logike prvog reda), koristit ćemo njihovu jezičnu reprezentaciju, ali to će biti nakon što objasnimo općenito kodiranje sa $\Sigma^*$ na $\N$ (i obrnuto).

Smatramo li nulu prirodnim brojem? Treba li brojenje početi od $0$ ili od $1$, dilema je stara koliko i samo računarstvo~\cite{note:EWD831}. Kao i drugdje u matematici, postoje dobri razlozi za obje opcije. Zato ćemo koristiti oba skupa, no kako će nam češće trebati nula među prirodnim brojevima (pogledajte na primjer definiciju od $\{0,1\}^*$), skup s nulom imat će kraću oznaku.
\begin{align}
    %\SwapAboveDisplaySkip
	\N&:=\{\mspace{2mu}0,1,2,3,\dotsc\}\nomenclature{$\N$}{skup prirodnih brojeva s nulom}\\
	\N_+&:=\{\mspace{2mu}1,2,3,4,\dotsc\}\nomenclature{$\N_+$}{skup pozitivnih prirodnih brojeva (bez nule)}
\end{align}

%\subsection{Broj izlaznih i ulaznih podataka}\label{sec:briup}

\begin{napomena}[{name=[samo jedan izlazni podatak]}]\label{nap:brip}
Govorili smo o izlaznim podacima u množini, no s obzirom na to da nas samo zanima postojanje algoritma, ništa ne gubimo fiksiranjem broja izlaznih podataka na $1$. Algoritam s $k$ ulaznih i $l$ izlaznih podataka uvijek možemo promatrati kao $l$ algoritama s istih $k$ ulaznih podataka i s po jednim izlaznim podatkom.

    Na primjer, u nekim programskim jezicima postoji operacija $\texttt{divmod}$ iz $\mathbb Z^2$ u $\mathbb Z^2$, koja provodi dijeljenje s ostatkom u $\mathbb Z$, vraćajući količnik i ostatak. Nju uvijek možemo, ako je nemamo kao osnovnu, emulirati pomoću dvije operacije, $\div$ i $\bmod$, koje vraćaju količnik i ostatak istog dijeljenja zasebno. Razlog zašto neki jezici imaju $\texttt{divmod}$ kao posebnu funkciju je u tome da algoritmi za te dvije operacije imaju mnogo zajedničkih koraka --- ako smo odredili količnik, obično možemo iz postupka kojim smo to učinili pročitati i ostatak (sjetite se npr.\ algoritma za dijeljenje višeznamenkastih brojeva). Zato bismo ponovnim provođenjem algoritma ispočetka za ostatak nepotrebno duplicirali korake. No ako nas samo zanima koje su funkcije izračunljive, očito postoji algoritam za $\texttt{divmod}$ ako i samo ako postoje algoritmi za \emph{koordinatne funkcije} $\div$ i $\bmod$, pa nam je dovoljno baviti se pitanjem jesu li $\div$ i $\bmod$ izračunljive --- u ovom slučaju, dakako, jesu.
\end{napomena}

Kad promatramo broj \emph{ulaznih} podataka (tzv\!.\ \emph{mjesnost}) algoritma, situacija je bitno drugačija. Jasno je da algoritam za npr.\ potenciranje prirodnih brojeva prima bazu i eksponent kao dva ulazna podatka, i ne može se jednostavno zapisati pomoću algoritama koji primaju po jedan ulazni podatak. %Doduše, korištenjem tehnike \emph{currying}, svaku izračunljivu funkciju možemo računati pomoću algoritama koji primaju po \emph{dva} ulazna podatka, i neki autori doista ograničavaju mjesnost na $2$, ali to stvara dosta tehničkih problema za minimalni dobitak.
Zato ćemo promatrati algoritme proizvoljnih mjesnosti $k\in\N_+$, i smatrati da mjesnost čini bitni dio identiteta algoritma. Primjerice, "zbroji dva broja" i "zbroji pet brojeva" su različiti algoritmi; štoviše, prvi od njih se pojavljuje kao korak (četiri puta) u drugome.

Posljedica toga je da u našem modelu ne postoje algoritmi s "varijabilnim brojem" ulaznih podataka, što je u računarstvu poznato pod nazivom \emph{varargs}. Na nekoliko mjesta gdje nam budu potrebni, modelirat ćemo ih pomoću familije algoritama svih mogućih mjesnosti --- recimo, zbrajanje kao $\f{add}^k,k\in\N_+$. Mjesnost\nomenclature{$\f f^k$}{brojevna funkcija mjesnosti $k$} algoritma ili funkcije ćemo obično pisati u superskriptu ako je želimo naglasiti --- neće dolaziti do zabune s eksponentima jer ni algoritme ni funkcije nećemo potencirati, niti s oznakom $f^{-1}$ za inverznu funkciju jer mjesnost ne može biti negativna.

Iako mjesnost smatramo neodvojivim dijelom funkcije odnosno algoritma, u slučaju nespecificirane mjesnosti $k$ nespretno je pisati $x_1,x_2,\dotsc,x_k$ kad god trebamo napisati argumente odnosno ulazne podatke. Zato ćemo često tih $k$ prirodnih brojeva skraćeno pisati $\vec x$\nomenclature{$\vec x$}{nekoliko argumenata čija su imena oblika $x_1$,~\dots,~$x_k$}, ili $\vec x^k$ ako želimo naglasiti koliko ih ima --- no najčešće će se to moći zaključiti iz konteksta: recimo, u $f^7(\vec x,y,z)$, vidimo da je duljina od $\vec x$ jednaka $5$.

\begin{napomena}[{name=[svi argumenti moraju biti eksplicitno navedeni]}]\label{nap:blokovi}
S obzirom na to da promatramo samo deterministične algoritme, naglasimo da nema "implicitnih argumenata": sve vrijednosti o kojima ovisi izlaz funkcije (ako se doista mijenjaju od poziva do poziva) moraju biti prenesene u nju kao argumenti. Često ćemo pisati opće funkcijske pozive kao $f(\vec x,y,z)$, gdje su $y$ i $z$ "pravi" argumenti s kojima doista nešto radimo u konkretnom algoritmu, a $\vec x$ predstavlja samo kontekst (\hspace{-1pt}\emph{environment}) nekog vanjskog algoritma koji je pozvao $f$ --- koji također moramo prenijeti u $f$ ako želimo da mu ona može pristupiti.
\end{napomena}

Pažljiv čitatelj će primijetiti da zahtijevamo da mjesnost bude pozitivna, odnosno ne promatramo algoritme s $0$ ulaznih podataka. Ovo nije bitna restrikcija (možete se zabaviti pokušavajući otkriti koje sve tehničke detalje u knjizi treba promijeniti da bismo uključili i takve algoritme u razmatranje), ali pojednostavljuje izlaganje, a takvi algoritmi nam nisu zanimljivi iz perspektive izračunljivosti: iz napomene~\ref{nap:blokovi} slijedi da nul-mjesni algoritmi mogu računati jedino konstante, a ne treba nam jako napredni formalizam da bismo zaključili da konstante \emph{jesu} izračunljive.

\subsection{Parcijalnost}

Gdje god je dosad bilo govora o općenitim izračunljivim funkcijama, namjerno je upotrijebljen prijedlog "iz": funkcija \emph{iz} $A$ u $B$. Općenito u matematici, takva fraza označava \emph{parcijalne} funkcije, koje ne moraju biti definirane u svim točkama od $A$ (precizno, domena im je podskup od $A$). Recimo, tangens je parcijalna funkcija iz $\mathbb R$ u $\mathbb R$, jer je $\frac{\pi}{2}\in\mathbb R\setminus \dom{\text{tg}}$. Takve funkcije označavamo oznakom $f:A\rightharpoonup B$, za razliku od \emph{totalnih} funkcija koje označavamo $f:A\to B$ i zovemo ih funkcije \emph{sa} $A$ u $B$. 

Dopuštajući algoritmima da računaju parcijalne funkcije, zapravo im omogućavamo da je za neke ulazne podatke njihov rad sasvim dobro definiran (dakle, ovdje ne mislimo na izuzetke, \emph{exceptions}, kao što je dijeljenje nulom), ali da ipak ne postoji završna konfiguracija iz koje bismo mogli pročitati izlazni podatak. Nakon malo razmišljanja dolazimo do zaključka da je to jedino moguće tako da algoritam za neke ulaze beskonačno radi, odnosno nikada ne stane.

\begin{napomena}[{name=[Russellov paradoks s totalnim algoritmima]}]\label{nap:diagtot}
	Nije li to u kontradikciji s naivnom definicijom algoritma, koja kaže da se radi o \emph{konačnom} postupku? Jest, ali to samo pokazuje da naivne definicije nisu dovoljne, i da nam treba formalizacija. Naivna definicija algoritma, baš kao i naivna definicija skupa, dovodi do paradoksa (Russell). \emph{Moramo} u obzir uzeti i parcijalne funkcije, odnosno algoritme koji ne stanu uvijek, ako želimo konzistentnu teoriju. Evo kratke skice argumenta --- precizno ćemo ga provesti u poglavlju~\ref{ch:ne}, kad precizno definiramo pojmove. Napomenimo samo da je argument specijalni slučaj općeg načina zaključivanja "ne postoji objekt koji sam sebe nadvladava", koji se često koristi u raznim granama matematike~\cite{url:tao}.

Budući da želimo algoritme moći reprezentirati u računalu, moramo ih moći prikazati kao konačne nizove nula i jedinica. Ta reprezentacija mora biti injekcija ako želimo razlikovati algoritme, a iz teorije skupova znamo da je $\{0,1\}^*$ prebrojiv\!, dakle \textbf{svih algoritama ima prebrojivo mnogo}. Specijalno, svih jednomjesnih algoritama ima prebrojivo mnogo (očito ih ima beskonačno mnogo). Poredajmo ih sve u niz, i pogledajmo ovaj jednomjesni algoritam:
\begin{quote}
	Za ulaz $x\in\N$, nađi $x$-ti algoritam u nizu, i primijeni ga na $x$.\\
	Izlaz tog algoritma (s ulazom $x$) označi s $y$. Vrati $y+1$.
\end{quote}
	Ako nacrtamo tablicu kojoj su retci jednomjesni algoritmi, a stupci ulazi za njih (prirodni brojevi), upravo opisani algoritam je klasična "promijenjena dijagonala" te tablice, koja se razlikuje od svakog njenog retka. Drugim riječima, \emph{taj algoritam ne može biti na popisu} ako algoritmi nužno računaju totalne funkcije --- ako je $r$-ti po redu, s ulazom $r$ morao bi davati i $y$ i $y+1$ --- ali s parcijalnim funkcijama nema kontradikcije, jer $r$-ti algoritam s ulazom $r$ ne mora stati.
\end{napomena}

Ipak, bitno je lakše raditi s algoritmima koji računaju totalne funkcije. Parcijalne funkcije moramo dozvoliti u krajnjoj općenitosti, ali mnoge funkcije koje ćemo koristiti u izgradnji teorije bit će ne samo totalne, nego i \emph{sintaksno} totalne unutar teorije koju gradimo: već iz oblika njihovih definicija bit će jasno da algoritmi koji ih računaju uvijek stanu. Takve funkcije zvat ćemo \emph{primitivno rekurzivnima}.

Recimo nekoliko riječi i o klasičnim izuzecima poput dijeljenja nulom. Primitivno rekurzivne funkcije moraju biti totalne pa si ne možemo priuštiti reći npr.\ "$3\div0$ nije definirano" (dokazat ćemo da je $\div$ primitivno rekurzivna operacija). U mnogim slučajevima to ćemo rješavati tako da kažemo "\emph{postoji} primitivno rekurzivna funkcija $\f{f}$ koja se podudara s traženom funkcijom $g$ na domeni $\dom{g}$", ne govoreći ništa o vrijednostima $\f{f}(\vec x)$ za $\vec x\notin\dom{g}$. %Još općenitije, ponekad ćemo umjesto funkcije $g$ navesti samo neko \emph{svojstvo} koje vrijednosti od $\f{f}$ moraju zadovoljavati na nekom skupu.
Kazat ćemo tada da smo \emph{parcijalno specificirali} (totalnu) funkciju $\f{f}$, u smislu: $\f{f}$ je definirana svuda, ali nas zanimaju samo njene vrijednosti na nekom užem skupu.

U ovoj knjizi precizno ćemo pisati algoritme --- ne pomoću pseudokoda, već formalnim konstrukcijama. Zato ćemo moći izračunati vrijednosti primitivno rekurzivne funkcije i izvan područja specifikacije --- na primjer, algoritam za $\div$ reći će nam da je $3\div 0=3$. Ponekad ćemo čak koristiti te "nedokumentirane značajke", jer će takvu funkciju biti lakše uklopiti u kasnije definicije bez rastava na slučajeve. %No to nećemo često koristiti, i svaki put ćemo naglasiti kad se to dogodi.

%\subsection{Relacije}

Iako sva računanja možemo shvatiti kao računanja funkcija, izlaganje je jednostavnije ako uvedemo i \emph{relacije}, koje ćemo računati kao posebni slučaj računanja funkcija. Iz standardne skupovnoteorijske perspektive to se čini čudnim: nisu li relacije općenit pojam, a funkcije samo posebni slučaj --- relacije s funkcijskim svojstvom?

Iz algoritamske perspektive, nisu. Ako izračunljivu funkciju $\f{f}$ reprezentiramo po\-mo\-ću algoritma koji za dani $\vec x$ računa njenu vrijednost $\f{f}(\vec x)$, izračunljivu relaciju $\f{R}$ prirodno je predstaviti algoritmom koji za dani $\vec x$ računa \emph{istinitosnu} vrijednost ($bool$: $\mathit{true}$ ili $\mathit{false}$), već prema tome je li $\vec x\in\f{R}$ ili nije. Većina programskih jezika nema mogućnost programiranja relacija kao zasebnog tipa algoritma, već ih reprezentiraju funkcijama čiji povratni tip je $bool$.

Na primjer, reći da je dvomjesna relacija uređaja $<$ na prirodnim brojevima iz\-ra\-čun\-lji\-va zapravo znači reći da postoji algoritam koji za sve ulaze $(x,y)\in\N^2$ u konačno mnogo koraka vraća $\mathit{true}$ ako je $x<y$, a $\mathit{false}$ inače. Ili, skup prim-brojeva (jednomjesna relacija $\mathbb P$) je izračunljiv jer možemo napisati algoritam $\f{isPrime}:\N\to bool$, koji za svaki $x$ u konačno mnogo koraka vraća $\mathit{true}$ ako je $x\in\mathbb P$, a $\mathit{false}$ ako $x\notin\mathbb P$. Iz navedenih primjera vidimo da je relacije prirodno katkad zamišljati kao formule s relacijskim simbolima ($\f{R}(\vec x)$, ili $x\mathrel{\f R}y$ za dvomjesne relacije), a katkad kao skupove ($\vec x\in\f{R}$).

U skladu s uobičajenom praksom mnogih programskih jezika, prešutno koristimo standardno ulaganje skupa $bool$ u $\N$, tako da preslikamo $\mathit{false}\mapsto 0$ i $\mathit{true}\mapsto 1$. Drugim riječima, na izračunljivost relacije $R$ gledamo kao na izračunljivost njene \emph{karakteristične funkcije} $\chi_R$, koja ima istu mjesnost kao $R$. U suprotnom smjeru koristimo (opet standardnu) interpretaciju nule kao $\mathit{false}$, a svih ostalih prirodnih brojeva kao $\mathit{true}$: drugim riječima, koristimo kompoziciju s karakterističnom funkcijom $\chi_{\N_+}$ (za koju ćemo dokazati da je izračunljiva).

Dakle, relacijama ćemo pripisivati svojstva izračunljivosti koja imaju njihove karakteristične funkcije: na primjer, reći ćemo da je $\f{R}$ primitivno rekurzivna ako je $\chi_{\f{R}}$ primitivno rekurzivna. Kod relacija ne moramo razmišljati o parcijalnosti: \textbf{karakteristične funkcije su uvijek totalne}. Relacije imaju drugi način modeliranja djelomične izračunljivosti, \emph{rekurzivnu prebrojivost} o kojoj će biti više riječi u poglavlju~\ref{ch:re}.

\section{Osnovni pojmovi i oznake}

Dakle, promatrat ćemo (algoritme za) dvije vrste funkcija: jezične i brojevne. Brojevne funkcije su nam važnije i uglavnom ćemo raditi s njima, ali na nekoliko mjesta dobro će nam doći i formalizacija izračunljivosti jezičnih funkcija.

Svaka brojevna funkcija je oblika $f:\N^k\rightharpoonup\N$ za neki $k\in\N_+$. Skraćeno pišemo $f^k$ i broj $k$ zovemo \emph{mjesnost} funkcije $f$. Svaka brojevna funkcija ima jedinstvenu mjesnost --- osim prazne funkcije $\varnothing$ s domenom $\emptyset$. Smatramo da i prazne funkcije imaju fiksnu mjesnost: umjesto jedne funkcije $\varnothing$ promatramo familiju $\varnothing^k,k\in\N_+$, proglašavajući na primjer $\varnothing^3$ i $\varnothing^8$ različitim funkcijama. Formalno to možemo napraviti tako da nam "funkcija" znači uređen par, kojem je prva komponenta uobičajena reprezentacija funkcije (skup uređenih parova~\ldots), a druga komponenta mjesnost --- ali nećemo biti toliko formalni, jer prazne funkcije nisu zanimljive iz perspektive izračunljivosti: računaju ih beskonačne petlje.

(Brojevna) relacija je oblika $R\subseteq\N^k$ za neki $k\in\N_+$. Po analogiji s funkcijama, $k$ zovemo \emph{mjesnost} relacije, i pišemo $R^k$ ako je želimo naglasiti. Kao i za funkcije, iako postoji samo jedan prazan skup, promatrat ćemo familiju $\emptyset^k,k\in\N_+$, smatrajući sve njene elemente različitim relacijama. Na kraju krajeva, njihove karakteristične funkcije \emph{jesu} različite, jer imaju različite domene: recimo, $\dom{\chi_{\emptyset^3}}\!=\N^3$. (Radi se o nulfunkciji $\f C_0^3:\N^3\to\N$; razlikujte nulfunkciju, koja je totalna, od prazne funkcije koja nije definirana nigdje!)

Jezične funkcije ćemo uvijek definirati nad nekom \emph{abecedom} (konačnim nepraznim skupom) $\Sigma$, kao funkcije $\varphi:\Sigma^*\rightharpoonup\Sigma^*$. Elementi od $\Sigma^*:=\bigcup_{k\in\N}\Sigma^k$ su \emph{riječi}: konačni nizovi \emph{znakova} iz $\Sigma$, koje pišemo konkatenacijom --- $\t{aab}$ umjesto $(\t{a},\t{a},\t{b})$. \emph{Prazna riječ} je niz duljine $0$: označavamo je s $\varepsilon$. Iz oblika jezičnih funkcija vidimo da su one jednomjesne: u svrhu reprezentacije funkcija veće mjesnosti, abecedi dodajemo \emph{separator} --- znak koji služi razdvajanju argumenata. Recimo, višemjesne funkcije nad $\{\t{a},\t{b}\}$ možemo reprezentirati kao jednomjesne funkcije nad $\{\t{a},\t{b},\t{,}\}$ --- tako da primjerice $\varphi^4(\t{a},\t{abb},\varepsilon,\t{ba})$ računamo kao $\varphi^1(\t{a{},{}a{}b{}b{},{},{}b{}a})$. Kažemo da je $\varphi^1$ dobivena \emph{kontrakcijom} iz $\varphi^4$. Ovo je malo općenitije od brojevnih višemjesnih funkcija jer možemo imati \emph{varargs} (mjesnost možemo odrediti brojenjem separatora u ulaznoj ri\-je\-či), ali i dalje nemamo nulmjesne funkcije: $\varphi(\varepsilon)$ je $\varphi^1(\varepsilon)$, ne $\varphi^0()$. %Sličan trik možemo primijeniti i kod brojevnih funkcija, nakon što definiramo kodiranje skupa $\N^*$.

Analogon pojmu relacije u jezičnom slučaju je \emph{jezik}: podskup od $\Sigma^*$. Iako karakteristična funkcija jezika nije ni brojevna ni jezična funkcija (ide sa $\Sigma^*$ u $bool$), svejedno možemo pomoću kodiranja skupa $\Sigma^*$ reprezentirati i izračunljivost jezik\=a. %O tome ćemo također više reći kasnije.

Domenu, sliku i graf funkcije $f$ označavamo redom s $\dom{f}$, $\im{f}$ i $\graf{f}$. To su relacije: za funkciju mjesnosti $k$, domena je mjesnosti $k$, slika je mjesnosti $1$, a graf je mjesnosti $k+1$. Iste oznake koristimo i za domene, slike i grafove funkcija koje nisu brojevne. Restrikciju funkcije $f$ na skup $S$ (zapravo na $S\cap\dom f$) označavamo s $f|_S$. Sliku te restrikcije za $S\subseteq\dom{f}$ označavamo s $f[S]:=\{f(x)\mid x\in S\}$. Prasliku skupa $T$ označavamo s $f^{-1}[T]:=\{x\in\dom{f}\mid f(x)\in T\}$. Ako je $f^k$ brojevna funkcija, oznakom $\tilde f$ označavamo njeno proširenje nulom: totalnu funkciju $\tilde{f}:\N^k\to\N$, koja svaki $\vec x\in\dom f$ preslika u $f(\vec x)$, a preostale $\vec x\in\N^k\setminus\dom f$ preslika u $0$. \emph{Nosač} brojevne funkcije $f$ je $f^{-1}[\N_+]$, dakle podskup domene na kojem $f$ nije $0$.

Za skupove brojeva koristimo standardne oznake $\mathbb P\subset \mathbb N\subset \mathbb Z\subset \mathbb Q\subset \mathbb R$. Često koristimo \emph{diskretne intervale}, koje označavamo $[a\dd b]$ ili $[a\dd b\rangle$, gdje su $a,b\in\N$. Svaki takav interval skup je prirodnih brojeva iz odgovarajućeg realnog intervala: na primjer, $[1\mspace{-1mu}\dd 5\rangle=[1\mspace{-2mu}\dd 4]=\{1,2,3,4\}$. Oznaka $A\dcup B$ označava uniju disjunktnih skupova (takvih da je $A\cap B=\emptyset$).

Brojevne izračunljive funkcije i relacije označavamo posebnim fontom: dok nam $g$ označava proizvoljnu funkciju, $\f{g}$ nam označava funkciju za koju imamo neku vrstu algoritma. U tom smislu, $g(x)$ označava uobičajenu funkcijsku vrijednost (drugu komponentu onog uređenog para iz skupa $g$ čija je prva komponenta $x$), dok $\f{g}(x)$ označava izlazni podatak algoritma za $\f{g}$ pokrenutog s ulaznim podatkom $x$. Ipak, to se odnosi samo na funkcijski zapis: inače ćemo koristiti uobičajene matematičke oznake gdje god možemo. Recimo, pisat ćemo $x+y+z$ za zbroj tri broja, $a^b$ za potenciranje, $m\mid n$ za djeljivost, ili pak $p\in\mathbb P$ za prim-brojeve. No treba imati na umu da su to izračunljive funkcije i relacije (što ćemo dokazati) te da u pozadini stoje algoritmi za $\f{add}^3$, $\f{pow}^2$, $\f{Divides}^2$, odnosno $\f{isPrime}^1$.

\begin{napomena}[{name=[jednakost i parcijalna jednakost]}]\label{nap:parcdef}
    Algoritmiziranu jednakost (izračunljivu dvomjesnu brojevnu relaciju, u modernim programskim jezicima često označenu \enquote*{\t{==}}) oz\-na\-ča\-va\-mo uobičajenim simbolom \enquote*{$\eq$} koji i inače koristimo za jednakost matematičkih objekata (funkcija, relacija, skupova,~\ldots). Kod definicija skupova, i funkcija s prethodno specificiranom domenom (posebno kod totalnih funkcija), koristimo simbol \enquote*{$:=$}. Relacije definiramo formulama koristeći \enquote*{$:\Longleftrightarrow$}. Često imamo potrebu vrijednosti funkcije specificirati izrazom, uz prešutnu pretpostavku "prirodne domene" (svi ulazni podaci za koje izraz ima vrijednost). Tada pišemo $f(\vec x):\simeq izraz$. Ovisno o obliku izraza, definirat ćemo precizno značenje fraze "imati vrijednost".
\end{napomena}

Znak $\simeq$ između dva izraza znači da oba imaju vrijednost za iste vrijednosti varijabli koje se u njima pojavljuju, i da su im tada vrijednosti jednake. Drugačije rečeno, $izraz1\simeq izraz2$ znači da su definicije $f(\vec x):\simeq izraz1$ i $f(\vec x):\simeq izraz2$ ekvivalentne (definiraju istu funkciju), gdje su u $\vec x$ sve varijable koje se pojavljuju u bilo kojem od ta dva izraza. Razlog za izbjegavanje korištenja znaka $\eq$ u takvom slučaju sastoji se u tome što relacija $\simeq$, kao i svojstvo "imati vrijednost" na izrazima, \textbf{nisu izračunljive}. Još jedan razlog za korištenje neuobičajenog znaka je što mnoga "instinktivna pojednostavljenja" više nisu ispravna. Na primjer, ako je $f^3$ totalna a $g^3$ nije, $f(\vec x)+0\cdot g(\vec x)\nsimeq f(\vec x)$ jer desni izraz ima vrijednost za sve $\vec x\in\N^3$, a lijevi samo za $\vec x\in\dom{g}$.

\section{RAM-stroj i RAM-program}\label{sec:RAMizr}

Prvi model izračunavanja koji ćemo promotriti --- \emph{RAM-stroj} --- dobiven je kao pojednostavljenje (gotovo karikatura) modernih računalnih procesora. Radi se o RISC-arhitekturi sa samo tri tipa instrukcija (jedan od kojih je eliminabilan, ali zadržat ćemo ga radi jednostavnosti izlaganja).

Ne pretpostavljamo nikakva ograničenja na broj dostupnih registara (pretpostavljamo da ih ima dovoljno za spremanje ulaznih i izlaznih podataka te za odvijanje programa --- svaki konkretni algoritam koristit će konačno mnogo \emph{relevantnih} registara, ali ne postavljamo gornju granicu s obzirom na sve algoritme) niti na veličinu pojedinog registra (u svakom trenutku izvršavanja algoritma, u svakom relevantnom registru može se nalaziti proizvoljni prirodni broj). Obje značajke nužne su već za reprezentaciju ulaza: postoje algoritmi proizvoljno velike mjesnosti, a moguće ih je pozvati s proizvoljno velikim ulaznim podacima.

Pretpostavljamo da je program \emph{fiksan}: ne može se mijenjati (tzv\!.\ \emph{harvardska} arhitektura). Iako k\=od koji sam sebe mijenja za vrijeme izvršavanja nije baš popularan na modernim računalnim arhitekturama (prvenstveno iz sigurnosnih razloga), osnovna ideja modernog računala je da "dovoljno nisko" imamo jedan procesor sposoban izvršavati razne programe (\emph{von Neumannova} arhitektura). Da bismo počeli koristiti drugi operacijski sustav\!, dovoljno je instalirati ga i ponovo pokrenuti računalo; ne moramo kupovati novi procesor.

Razlog zašto radimo s ograničenijim modelom je što von Neumannova arhitektura \emph{pretpostavlja} univerzalnost, koju mi tek trebamo dokazati. To ćemo i učiniti, ali tek u poglavlju~\ref{ch:univ}. Krenimo s osnovnim definicijama.

%\section{RAM-stroj i RAM-program}\label{sec:RAMizr}

\begin{definicija}[{name=[RAM-stroj]}]
\emph{RAM-stroj} je matematički (idealizirani) stroj, koji sadrži:
\begin{itemize}
    \item \emph{RAM-program}: fiksni konačni niz \emph{instrukcija} $P:=(I_0,I_1,I_2,~\dotsc, I_{n-1})$;
    \item \emph{registre}: za svaki $j\in\N$, registar $\reg{j}$, koji može sadržavati bilo koji prirodni broj;
    \item \emph{programski brojač} (\textsc{pc}): još jedan "registar", koji u svakom trenutku iz\-ra\-ču\-na\-va\-nja sadrži broj iz intervala $[0\dd n]$.
    \qedhere
\end{itemize}
\end{definicija}
%\vspace{-1em}

RAM-program najčešće pišemo kao %\begin{equation}
$P:=\begin{prog}
    0.&I_0\\
    1.&I_1\\
    &\vdots\\
    (n-1).&I_{n-1}
    \end{prog}$, ili skraćeno $P:=\begin{prog}
    t.&I_t
    \end{prog}_{t<n}$.\\
%\end{equation}
Broj instrukcija programa $P$ zovemo još \emph{duljinom} programa $P$, i označavamo ga s $n_P$.

Sadržaj registara se može mijenjati za vrijeme izvršavanja programa, u skladu s instrukcijama. Početni sadržaj određen je ulaznim podacima. Irelevantni registri (koji se ne spominju u instrukcijama niti služe za ulaz) formalno sadrže vrijednost $0$, iako (po definiciji irelevantnosti) zapravo nije bitno koju vrijednost sadrže.

Sadržaj programskog brojača također se mijenja, tako da se iz\-vr\-ša\-va\-njem svake instrukcije poveća za $1$, osim ako sama instrukcija kaže drugačije. Početna vrijednost programskog brojača je $0$. U svakom trenutku sadržaj programskog brojača je redni broj instrukcije koja se trenutno izvršava, dok vrijednost $n$ označava kraj izvođenja programa.

\begin{definicija}[{name=[RAM-instrukcija]}]\label{def:ins}
Svaka \emph{RAM-instrukcija} ima:
\begin{itemize}
    \item (ako je dio RAM-programa $P$) \emph{redni broj}, element skupa $[0\dd n_P\rangle$;
    \item \emph{tip}, koji može biti: \inc\ (\hspace{-1pt}\emph{inkrement}\/), \dec\ (\hspace{-1pt}\emph{dekrement}\/) ili \goto\ (\hspace{-1pt}\emph{skok}\/);
    \item (ako je tipa \inc\ ili \dec) registar na kojem djeluje: $\reg{j}$ za neki $j\in\N$;
    \item (ako je tipa \dec\ ili \goto\ te je dio RAM-programa $P$) \emph{odredište}: \\ element skupa $[0\dd n_P]$.
    \qedhere
\end{itemize}
\end{definicija}

Dakle, RAM-instrukcija može biti jednog od tri oblika (s navedenim učincima):
\begin{labeling}{$\decr{j}{l}$:}
    \item[$\incr{j}$:] Povećava sadržaj registra $\reg{j}$ za $1$.
    \item[$\decr{j}{l}$:] Ako je sadržaj od $\reg{j}$ pozitivan, smanjuje ga za $1$. Inače postavlja \textsc{pc} na $l$.
    \item[$\goto\;l$:] Postavlja \textsc{pc} na $l$.
\end{labeling}

\begin{lema}[{name=[prebrojivost skupa $\mathscr Ins$]}]\label{lema:alef0ins}
Skup $\mathscr Ins$ svih RAM-instrukcija je prebrojiv\!.
\end{lema}
\begin{proof}
Skup $\mathscr Ins_{\inc}$ svih instrukcija tipa $\inc$ je prebrojiv: preslikavanje $f_1:\N\to\mathscr Ins_\inc$ zadano s $f_1(j):=(\incr{j})$ je bijekcija. Analogno, koristeći odredište (iako je broj odredišta ograničen za fiksni program $P$, svaka instrukcija $\goto\;l$ se može pojaviti u \emph{nekom} programu), skup $\mathscr Ins_{\goto}$ je prebrojiv\!, a skup $\mathscr Ins_\dec$ je ek\-vi\-po\-ten\-tan s $\N\times\N$, pa je i on prebrojiv\!. Sada je $\mathscr Ins$ prebrojiv kao (disjunktna) unija tih triju prebrojivih skupova.
\end{proof}

\begin{korolar}[{name=[prebrojivost skupa $\mathscr Pr\mspace{-1mu}o\mspace{-2mu}g$]}]\label{kor:alef0prog}
	Skup $\mathscr Pr\mspace{-1mu}o\mspace{-2mu}g$ svih RAM-programa je prebrojiv\!.
\end{korolar}
\begin{proof}
	To slijedi iz činjenice da je $\mathscr Ins_{\inc}^{\quad*}\subseteq\mathscr Pr\mspace{-1mu}o\mspace{-2mu}g\subseteq\mathscr Ins^*$, i leme~\ref{lema:alef0ins}. Iz teorije skupova znamo da je skup $A^*$ prebrojiv ako je $A$ prebrojiv\!.
\end{proof}

%\subsection{Konfiguracije i izračunavanja}

Jednom kad imamo definirane instrukcije, program i stroj, možemo preciznije definirati kako stroj izvršava program, odnosno o kakvom se točno algoritmu tu radi.

\begin{definicija}[{name=[RAM-konfiguracije i prijelazi među njima]}]\label{def:RAMconf}
Neka je $\mathcal S$ RAM-stroj s programom $P$, registrima $\reg j,j\in\N$ te programskim brojačem \textsc{pc}. \emph{Konfiguracija} RAM-stroja $\mathcal S$ je bilo koje preslikavanje
\begin{equation}
    c:\{\reg{j}\mid j\in\N\}\dcup\{\textsc{pc}\}\to\N
\end{equation} takvo da je skoro svuda $0$ (skup $c^{-1}[\N_+]$ je konačan), a $c(\textsc{pc})\le n_P$. Skraćeno je pišemo kao $c=\bigl(c(\reg0),c(\reg1),\dotsc,c(\textsc{pc})\bigr)$. Konfiguracija $c$ je \emph{završna} ako je $c(\textsc{pc})=n_P$. \emph{Početna konfiguracija} s ulazom $\vec x=(x_1,x_2,\dotsc,x_k)\in\N^k$ je $(0,x_1,x_2,\dotsc,x_k,0,0,\dotsc,0)$ (u $\reg j$ je $x_j$ za $j\in[1\mspace{-1mu}\dd k]$, a svugdje drugdje su nule).

    Za konfiguracije $c=(r_0,r_1,\dotsc,pc)$ i $d=(r_0',r_1',\dotsc,pc')$ istog RAM-stroja s programom $P=(I_0,\dotsc,I_{n_P-1})$, kažemo da $c$ \emph{prelazi} u $d$ (\emph{po programu} $P$, ili \emph{po instrukciji} $I_{pc}$), i pišemo $c\leadsto d$, ako vrijedi jedno od sljedećeg:
\begin{enumerate}
    \item\label{stav:leadzav}
    $c$ je završna ($pc=n_P$) i $c=d$ --- to skraćeno pišemo $c\!\lcirclearrowleft$\!;
    \item\label{stav:leadINC}
    $I_{pc}=\incr{j}$ (za neki $j$), $r_j'=r_j+1$, $pc'=pc+1$ te $r'_i=r_i$ za sve $i\ne j$;
    \item\label{stav:leadDEC-}
    $I_{pc}=\decr{j}{l}$ (za neke $j$ i $l$),  $r_j'=r_j-1$, $pc'=pc+1$ te $r'_i=r_i$ za sve $i\ne j$;
    \item\label{stav:leadDEC0}
    $I_{pc}=\decr{j}{l}$ (za neke $j$ i $l$), $r_j=0$, $pc'=l$ te $r'_i=r_i$ za sve $i$;
    \item\label{stav:leadGOTO}
    $I_{pc}=\goto\;l$ (za neki $l$), $pc'=l$ te $r'_i=r_i$ za sve $i$.\qedhere
\end{enumerate}
\end{definicija}

Često ćemo objašnjavati semantiku instrukcija (kad uvedemo dodatne instrukcije) na gornji način. Pri tome se držimo dogovora da je konfiguracija prije izvođenja instrukcije označena oznakama bez crtica, a ona nakon izvođenja instrukcije oznakama s crticama. Također smatramo da je $r'_i=r_i$ za sve $i$ koji nisu navedeni, a $pc'=pc+1$ ako nije rečeno drugačije. Uz taj dogovor, semantika instrukcije $\incr{j}$ se može zapisati kao $r_j'=r_j+1$, semantika instrukcije $\goto\;l$ kao $pc'=l$, a semantika instrukcije $\decr jl$ kao: ako je $r_j>0$, tada $r_j'=r_j-1$, a inače $pc'=l$.

Sada možemo formalizirati determinističnost RAM-stroja.

\begin{lema}[{name=[determinističnost RAM-stroja]}]\label{lema:ramdet}
Svaka konfiguracija prelazi u neku, jedinstvenu, konfiguraciju.
\end{lema}
\begin{proof}
    Neka je $\mathcal S$ RAM-stroj s programom $(I_0, I_1,\dotsc, I_{n-1})$ te $c=(r_0,r_1,\dotsc,pc)$ njegova proizvoljna konfiguracija. Po definiciji je $pc\le n$ --- ako vrijedi jednakost, $c$ je završna pa po pravilu~\ref{stav:leadzav} prelazi u samu sebe (nijedno drugo pravilo nije primjenjivo jer $I_{pc}$ ne postoji). Ako je pak $pc<n$, pogledajmo tip od $I_{pc}$. Ako je to $\inc$ ili $\goto$, pravilo~\ref{stav:leadINC} odnosno~\ref{stav:leadGOTO} točno propisuje novu konfiguraciju u koju $c$ prelazi.

    Inače, $I_{pc}$ je tipa $\dec$, recimo $\decr{j}{l}$, i tada je opet nova konfiguracija jedinstveno određena, s obzirom na $r_j$. Ako je $r_j>0$ ("istina"), tada je primjenjivo samo pravilo~\ref{stav:leadDEC-}, a ako je $r_j=0$ ("laž"), tada je primjenjivo samo pravilo~\ref{stav:leadDEC0}; pravilo~\ref{stav:leadDEC-} nije primjenjivo jer po definiciji konfiguracije mora biti $r_j'\in\N$, a primjenom pravila~\ref{stav:leadDEC-} bismo dobili $r_j'=-1$. Svako od tih pravila također jednoznačno određuje novu konfiguraciju.
\end{proof}

\begin{definicija}[{name=[{RAM-algoritam, izračunavanje i računanje funkcije}]}]
\label{def:compute}
\emph{RAM-algoritam} je uređen par RAM-programa $P$ i mjesnosti $k\in\N_+$. Umjesto $(P,k)$ pišemo $P^k$.

Neka je $P^k$ RAM-algoritam te $\vec x\in\N^k$. \emph{$P$\!-izračunavanje s $\vec x$} je niz konfiguracija $(c_n)_{n\in\N}$, takvih da je $c_0$ početna konfiguracija (stroja s programom $P$) s ulazom $\vec x$ te, za svaki $n$, $c_n$ prelazi u $c_{n+1}$. Kažemo da to izračunavanje \emph{stane} ako postoji $n_0\in\N$ takav da je $c_{n_0}$ završna.

Neka je $P^k$ RAM-algoritam te $f^k$ brojevna funkcija iste mjesnosti. Kažemo da $P^k$
\emph{računa} funkciju $f$ ako za sve $\vec x\in\N^k$ vrijedi:
\begin{itemize}
    \item ako  je $\vec x\in \dom{f}$, tada $P$-izračunavanje s $\vec x$ stane u konfiguraciji oblika $(f(\vec x),\dotsc,n_P)$;
    \item u suprotnom (ako $\vec x\notin\dom{f}$), $P$-izračunavanje s $\vec x$ ne stane.\qedhere
\end{itemize}
\end{definicija}

Drugim riječima, $P$-izračunavanje s $\vec x$ stane točno onda kada je $\vec x\in\dom{f}$ --- i u tom slučaju, u završnoj konfiguraciji, sadržaj registra $\reg{0}$ je vrijednost funkcije $f$ u točki $\vec x$.

\subsection{Skup \texorpdfstring{$\mathscr Comp$}{Comp}}

Navodimo tri lagane posljedice determinizma.

\begin{propozicija}[{name=[jedinstvenost izračunavanja]}]\label{prop:ramdet}
Za svaki RAM-algoritam $P^k$, za svaki ulaz $\vec x\in\N^k$,\\ postoji jedinstveno $P$-izračunavanje s $\vec x$.
\end{propozicija}
\begin{proof}
Za postojanje, induktivno definiramo
\begin{align}
    c_0&:=\text{početna konfiguracija s ulazom $\vec x$,}\\
    c_{n+1}&:=\text{jedinstvena konfiguracija u koju $c_n$ prelazi (prema lemi~\ref{lema:ramdet}).}
\end{align}
Po Dedekindovu teoremu rekurzije, time je dobro definiran niz, i taj niz je po definiciji $P$-iz\-ra\-ču\-na\-va\-nje s $\vec x$.

Za jedinstvenost, pretpostavimo da postoje dva $P$-izračunavanja s $\vec x$, $(c_i)_{i\in\N}$ i $(c_i')_{i\in\N}$.
Kako je $c\ne c'$, postoji neki $i\in\N$ takav da je $c_i\ne c_i'$, a zbog dobre uređenosti od $\N$ postoji najmanji takav: označimo ga s $i_0$.
Taj $i_0$ nije $0$, jer je $c_0=c_0'=\text{početna konfiguracija s ulazom $\vec x$}$. Dakle, konfiguracija $c_{i_0-1}=c_{i_0-1}'$ prelazi u dvije različite konfiguracije $c_{i_0}$ i $c_{i_0}'$, što je kontradikcija s lemom~\ref{lema:ramdet}.
\end{proof}

\begin{propozicija}[{name=[jedinstvenost završne konfiguracije]}]\label{prop:ram1zav}
U svakom RAM-izračunavanju koje stane postoji jedinstvena završna konfiguracija.
\end{propozicija}
\begin{proof}
Pretpostavimo da je $(c_i)_{i\in\N}$ $P$-izračunavanje s $\vec x$ u kojem postoje dvije završne konfiguracije, i označimo s $i_1$ i $i_2$ indekse na kojima se one prvi put pojavljuju. Bez smanjenja općenitosti (različitost je simetrična) možemo pretpostaviti $i_1<i_2$. No budući da je $c_{i_1}$ završna, ona prelazi (samo) u samu sebe, pa indukcijom imamo
\begin{equation}
    c_{i_1}=c_{i_1+1}=c_{i_1+2}=\dotsb=c_{i_2}\text,
\end{equation}
kontradikcija.
\end{proof}

\begin{korolar}[{name=[svaki RAM-algoritam računa jedinstvenu funkciju]}]\label{kor:ram1fun}
Svaki RAM-algoritam računa jedinstvenu brojevnu funkciju.
\end{korolar}
\begin{proof}
	Neka je $(P,k)$ proizvoljni RAM-algoritam: $P$ je RAM-program te $k\in\N_+$. Definirajmo% skup
\begin{align}
S&:=\{\vec x\in\N^k\mid\text{$P$-izračunavanje s $\vec x$ stane}\}
\intertext{i na tom skupu funkciju}
f(\vec x)&:=c(\reg{0})\text{, gdje je $c$ završna konfiguracija $P$-izračunavanja s $\vec x$.}
\end{align}
Iz te definicije slijedi da je $f:S\to\N$ ($k$-mjesna) brojevna funkcija, a $P^k$ računa $f$.

Za jedinstvenost, mjesnost funkcije je određena mjesnošću algoritma (uz prethodni dogovor da se prazne funkcije različitih mjesnosti razlikuju), njena domena je određena stajanjem izračunavanja (jedinstvenog zbog propozicije~\ref{prop:ramdet}), a vrijednost funkcije u svakoj točki domene određena je završnom konfiguracijom (jedinstvenom zbog propozicije~\ref{prop:ram1zav}).
\end{proof}

Važna posljedica prethodnog rezultata je ograničenje broja izračunljivih funkcija.

\begin{definicija}[{name=[{RAM-izračunljiva funkcija, skup $\mathscr Comp$}]}]\label{def:ram-izr}
Neka je $k\in\N_+$ te $f^k$ brojevna funkcija. Kažemo da je $f^k$ \emph{RAM-izračunljiva} ako postoji RAM-algoritam $P^k$ koji je računa. Za svaki $k\in\N_+$, oznakom $\mathscr Comp_k$ označavamo skup svih RAM-izračunljivih funkcija mjesnosti $k$.
\end{definicija}

Oznaka $\mathscr Comp_k$ namjerno ne spominje RAM-model izračunavanja --- pokazat ćemo da se \emph{isti} skup brojevnih funkcija dobije i u drugim modelima koje ćemo razmatrati.

\begin{teorem}[{name=[prebrojivost skupa $\mathscr Comp$]}]\label{tm:alef0izr}
Za svaki $k\in\N_+$, skup $\mathscr Comp_k$ je prebrojiv\!. Skup $\mathscr Comp$ svih RAM-izračunljivih brojevnih funkcija (svih mjesnosti) je također prebrojiv\!.
\end{teorem}
\begin{proof}
Neka je $k$ fiksna mjesnost. Preslikavanje
	sa skupa $\mathscr Pr\mspace{-1mu}o\mspace{-2mu}g$ na skup $\mathscr Comp_k$,
	koje svakom RAM-programu $P$ pridružuje funkciju koju algoritam $P^k$ računa, je dobro definirano prema korolaru~\ref{kor:ram1fun}, i surjekcija je po definiciji~\ref{def:ram-izr}. Iz toga je $\card(\mathscr Comp_k)\le\card(\mathscr Pr\mspace{-1mu}o\mspace{-2mu}g)$, što je $\aleph_0$ po korolaru~\ref{kor:alef0prog}.

Za drugu nejednakost uočimo da su, za sve $n\in\N$ i $k\in\N_+$, konstantne funkcije zadane s
$\f{C}_n^k(\vec x):=n$, RAM-izračunljive: doista, računaju ih RAM-algoritmi
\begin{equation}\label{eq:konstRAM}
    P_n^k:=\begin{prog}
    t.&\incr0
    \end{prog}_{t<n}^k=\begin{prog}
    0.&\incr{0}\\
    1.&\incr{0}\\
    &\vdots\\
    (n-1).&\incr{0}
    \end{prog}^k
\end{equation}
(što se može vidjeti indukcijom po $n$).
Iz toga slijedi da je $\{\f{C}_n^k\mid n\in\N\}\subseteq\mathscr Comp_k$, a kako je taj skup prebrojiv (sve konstante su različite), slijedi $\aleph_0\le\card(\mathscr Comp_k)$, što zajedno s gornjim daje $\card(\mathscr Comp_k)=\aleph_0$.

Sada je $\mathscr Comp=\bigcup_{k\in\N_+}\!\mathscr Comp_k$ prebrojiv kao unija prebrojivo mnogo prebrojivih skupova.
\end{proof}

\begin{korolar}[{name=[postojanje ne-RAM-izračunljivih funkcija]}]\label{kor:exneizrk}
Za svaki $k\in\N_+$ postoji brojevna funkcija mjesnosti $k$ koja nije RAM-izračunljiva.
\end{korolar}
\begin{proof}
Opet, fiksirajmo mjesnost $k\in\N_+$. Skup svih $k$-mjesnih brojevnih funkcija $\mathscr Func_k$ je neprebrojiv\!, jer je nadskup skupa svih \emph{totalnih} $k$-mjesnih brojevnih funkcija, čija je kardinalnost
\begin{equation}
    \card\bigl(\N^{\N^k}\bigr)=\aleph_0^{\aleph_0^k}=\aleph_0^{\aleph_0}=\mathfrak c>\aleph_0\text.
\end{equation}
    Iz toga i teorema~\ref{tm:alef0izr} slijedi $\mathscr Func_k\nsubseteq\mathscr Comp_k$, pa je $\mathscr Func_k\!\setminus\mathscr Comp_k\ne\emptyset$.
\end{proof}

\subsection{Primjeri RAM-programa}

RAM-programe za konstantne funkcije vidjeli smo već u dokazu teorema~\ref{tm:alef0izr}. Specijalno, za $n=0$, \emph{prazan program} $[\,]$ računa \emph{nulfunkciju} $\f{C}_0^k$ za svaki $k\in\N_+$. Dakle, prazan program nažalost ne računa praznu funkciju --- što bi bilo lako zapamtiti --- ali računa \emph{praznu relaciju} $\emptyset^k$, odnosno njenu karakterističnu funkciju. Također, za $n=1$, program $\begin{prog}0.&\incr0\end{prog}$ računa univerzalnu relaciju $\N^k$.

Napišimo RAM-program koji računa praznu funkciju $\varnothing^k$. Po definiciji, to je program čije izračunavanje ne stane ni s kojim ulazom. %Iz definicije zaključujemo da je to program čije izračunavanje s $\vec x$ ne stane ni za koji $\vec x$ (bez obzira na mjesnost).
Dakle, moramo spriječiti $\textsc{pc}$ da dođe do $n$, odnosno treba nam instrukcija s odredištem, koja će vratiti $\textsc{pc}$ na staru vrijednost tako da se ne poveća za $1$ (\emph{petlja}), i to ona koja se izvrši uvijek (\emph{beskonačna} petlja). Takav program je $\begin{prog}0.&\goto\;0\end{prog}$.

Dosadašnji programi nisu uopće koristili svoje ulaze. Najjednostavnija funkcija koja koristi svoj argument je identiteta (označena s $\f I_1^1$). Da bismo je izračunali, moramo prebaciti vrijednost iz ulaznog registra $\reg{1}$ u izlazni registar $\reg{0}$. Koristeći naše razumijevanje izvršavanja imperativnih programa, vidimo da to čini RAM-algoritam
\begin{equation}\label{eq:RAMid}
    P_{\f I_1}^1:=\begin{prog}
        0.&\decr13\\
        1.&\incr0\\
        2.&\goto\;0
    \end{prog}^1\text.
\end{equation}
Formalno, mogli bismo dokazati da svaki prolaz kroz petlju (čitanje instrukcija redom) počevši od konfiguracije u kojoj je $r_1>0\land pc=0$ ima semantiku $r_1'=r_1-1\land r_0'=r_0+1\land pc'=0$. Ako je $r_1=0$, izvršavanje instrukcije rednog broja $0$ završava izračunavanje, jer $pc$ postane jednak duljini programa, $3$. Iz toga se onda indukcijom po $r_1$ može zaključiti da je semantika čitavog programa $r_1'=r_1-r_1=0\land r_0'=r_0+r_1$, pa iz početne konfiguracije s ulazom $x$, $(0,x,0,\dotsc,0)$, dolazimo u završnu konfiguraciju $(x,0,0,\dotsc,3)$ s izlaznim podatkom $x$. Na primjer, za $x=2$ imamo sljedeću "šetnju" kroz konfiguracije:
\begin{multline}
    (0,2,0,\dotsc,0)\leadsto
    (0,1,0,\dotsc,1)\leadsto
    (1,1,0,\dotsc,2)\leadsto
    (1,1,0,\dotsc,0)\leadsto\\
    \leadsto(1,0,0,\dotsc,1)\leadsto
    (2,0,0,\dotsc,2)\leadsto
    (2,0,0,\dotsc,0)\leadsto
    (2,0,0,\dotsc,3)\lcirclearrowleft\text.
\end{multline}

Ubuduće nećemo biti tako precizni (upravo jer imamo razvijen osjećaj za programiranje u imperativnim jezicima), ali ćemo navesti "najvažnije trenutke" u iz\-ra\-ču\-na\-va\-nju kako bi bilo lakše pratiti što se događa.

Prethodni dokaz (ili programerska intuicija) daje nam i više: ako "naslažemo" (konkateniramo) više takvih blokova za različite ulazne registre, možemo dobiti RAM-programe za zbrajanje. Konkretno, funkcija $\f{add}^3$ zadana s $\f{add}(x,y,z):=x+y+z$ je RAM-izračunljiva, jer je računa RAM-algoritam
\vspace{-1em}
\begin{equation}\label{eq:add3}
	P_{\!\!\f{add}^3}^{\;3}:=\begin{prog}
        0.&\decr13\\
        1.&\incr0\\
        2.&\goto\;0\\
        3.&\decr26\\
        4.&\incr0\\
        5.&\goto\;3\\
        6.&\decr39\\
        7.&\incr0\\
        8.&\goto\;6
    \end{prog}^3\text.
\end{equation}

Vidimo jednu dobru stranu naizgled čudne konvencije da izračunavanje za\-vr\-ša\-va kad programski brojač postane jednak duljini programa: prilikom ovakve konkatenacije ne trebamo mijenjati odredišta već napisanih instrukcija. Odredište $3$ instrukcije rednog broja $0$ jednako je označavalo kraj programa~\eqref{eq:RAMid} za $\f{I}_1^1$, kao i kraj \emph{tog dijela} programa za $\f{add}^3$. Primijetite sličnost sa standardnom konvencijom o \texttt{end}-iteratoru u biblioteci STL jezika C\texttt{++}.

Vidjeli smo da su mnoge funkcije (prazna, konstante, identiteta, zbrajanje,~\ldots) RAM-izračunljive. Ipak, pisati RAM-programe može biti dosta zamorno (na primjer za $\f{add}^8$ --- mnogi dijelovi se ponavljaju uz neznatne izmjene u odredištima ili adresama registara) ili komplicirano (na primjer za množenje, ili potenciranje --- povremeno bismo htjeli iskoristiti registar kao brojač za neku petlju, ali istodobno i sačuvati njegovu vrijednost). Prvi problem riješit ćemo makroima, a drugi funkcijskim programiranjem u poglavlju~\ref{ch:rek}.

\section{Makro-izračunljivost}

Izvršavanje RAM-programa na RAM-stroju, pored prevođenja početne konfiguracije (s ulazom $\vec x$) u završnu (s izlazom $\f{f}(\vec x)$), proizvede mnoge "popratne učinke" (\emph{side-effects}) na njegovim registrima. Te učinke možemo objediniti (\emph{enkapsulirati}) tako da čitav RAM-program $P$ shvatimo kao jednu instrukciju $P^*$ nekog kompliciranijeg stroja. 

Ta oznaka sugerira dualnu upotrebu RAM-programa $P$: ako ga koristimo radi računanja $k$-mjesne funkcije ($k$ ulaznih registara), promatramo ga kao algoritam $P^k$, a ako ga koristimo radi djelovanja na registre (svi registri "ulazni"), promatramo ga kao \emph{makro} $P^*$.

Primjerice, za svaki $j\in\N$, RAM-program $P_j:=\begin{prog}
0.&\decr j2\\
1.&\goto\;0
\end{prog}$ ima semantiku $r_j'=0$ (njegovo izvršavanje postavlja $\reg{j}$ na nulu --- kažemo da \emph{resetira} $\reg j$). To znači da imamo makro $P_j^*$ koji kasnije možemo koristiti u \emph{makro-programima} za resetiranje jednog registra bez promjene ostalih. Taj makro zovemo $\textsc{zero}\;\reg{j}$.

Definirat ćemo brojne makroe, što će kulminirati \emph{funkcijskim makroom} --- koji pruža mogućnost da naš programski jezik, kojim pišemo makro-programe, izvršava prave funkcijske pozive, sa zasebnim okvirom (\emph{scope}) lokalnih varijabli, prijenosom argumenata po vrijednosti, i zapisivanjem povratne vrijednosti u po volji odabrani registar, čuvajući sadržaje registara koji su nam bitni. Za početak navedimo osnovne definicije i tvrdnje koje vrijede za makro-paradigmu. Gotovo sve one su sasvim analogne onima u RAM-paradigmi, pa ih nećemo detaljno motivirati odnosno obrazlagati.

\begin{definicija}[{name=[makro-stroj]}]
\emph{Makro-stroj} je matematički stroj koji sadrži:
\begin{itemize}
    \item \emph{makro-program}: fiksni konačni niz \emph{makro-instrukcija} $Q:=(I_0, I_1,~\dotsc, I_{n-1})$,\\ svaka od kojih je jednog od dva oblika:
    \begin{itemize}
        \item obična RAM-instrukcija (tipa $\inc$, $\dec$ ili $\goto$), ili
        \item  \emph{makro} oblika $P^*$, gdje je $P$ RAM-program;
    \end{itemize}
    \item registre $(\reg j)_{j\in\N}$, iste kao i kod RAM-stroja;
    \item programski brojač $\textsc{pc}$, isti kao i kod RAM-stroja;
    \item \emph{pomoćni programski brojač} $\textsc{ac}$, čije  moguće vrijednosti $ac$ ovise o makro-instrukciji koja se trenutno izvršava ($I_{pc}$, gdje je $pc$ vrijednost od \textsc{pc}):
    \begin{itemize}
        \item ako je $I_{pc}=P^*$ za RAM-program $P$, tada je $ac\in[0\dd n_P]$;
        \item inače ($pc=n_Q$, ili $I_{pc}\!\in\mathscr Ins$), $ac=0$.\qedhere
    \end{itemize}
\end{itemize}
\end{definicija}
\noindent Sada možemo, slično kao lemu~\ref{lema:alef0ins} i korolar~\ref{kor:alef0prog}, dokazati da su skupovi
\begin{align}
	\mathscr{MI}ns&:=\mathscr Ins\mathbin{\dcup}\{P^*\mid P\in\mathscr Pr\mspace{-1mu}o\mspace{-2mu}g\}\text{, i}\\
	\mathscr{MP}r\mspace{-1mu}o\mspace{-2mu}g&:=\{Q\in\mathscr{MI}ns^*\mid\text{sva odredišta u $Q$ su manja ili jednaka $n_Q$}\}\text,
\end{align}
svih makro-instrukcija, i svih makro-programa, prebrojivi. Ti rezultati nisu toliko bitni zbog tehnika koje ćemo uskoro razviti, ali predstavljaju dobru vježbu. % Sljedeći korak u tom smjeru je konstatacija da makro-izračunljivih funkcija ima prebrojivo mnogo, i kao posljedica toga, postoje brojevne funkcije koje nisu ni makro-izračunljive. No

% \subsection{Konfiguracije i izračunavanja}

\begin{definicija}[{name=[makro-konfiguracija]}]\label{def:macroconf}
\emph{Konfiguracija makro-stroja} s programom $Q=(I_0,I_1,\dotsc,I_{n_Q-1})$, registrima $\reg{j}$, $j\in\N$ te programskim brojačima $\textsc{pc}$ i $\textsc{ac}$ je bilo koje preslikavanje $c:\{\reg{j}\mid j\in\N\}\dcup\{\textsc{pc},\textsc{ac}\}\to\N$, takvo da je $c^{-1}[\N_+]$ konačan skup, $c(\textsc{pc})\le n_Q$, i još vrijedi $c(\textsc{ac})=0$ --- osim u slučaju $I_{c(\textsc{pc})}=P^*$, kada je $c(\textsc{ac})\le n_P$. Skraćeno pišemo $c=\bigl(c(\reg0),c(\reg1),\dotsc,c(\textsc{pc}),c(\textsc{ac})\bigr)$.

Početna makro-konfiguracija s ulazom $\vec x$ definira se jednako kao i početna RAM-konfiguracija: svuda osim na ulaznim registrima je $0$, pa tako i na $\textsc{ac}$. Također, završna makro-konfiguracija definira se jednako kao i u RAM-slučaju: uvjetom $c(\textsc{pc})=n_Q$ (tada mora biti $c(\textsc{ac})=0$, jer $I_{c(\textsc{pc})}$ uopće ne postoji).
\end{definicija}

\begin{definicija}[{name=[prijelazi među makro-konfiguracijama]}]\label{def:makrolead}
Za konfiguracije $c=(r_0,r_1,\dotsc,pc,ac)$ i $d=(r_0',r_1',\dotsc,pc',ac')$ istog makro-stroja s makro-programom $Q=(I_0,I_1,\dotsc,I_{n_Q-1})$, kažemo da $c$ \emph{prelazi} u $d$ (\emph{po programu} $Q$), i pišemo $c\leadsto d$, ako vrijedi jedno od sljedećeg:
\begin{enumerate}
    \item\label{stav:zav} $c=d$, i $c$ je završna konfiguracija ($pc=n_Q$) --- još pišemo $c\!\lcirclearrowleft$;
    \item\label{stav:Q} $ac=ac'=0$, $I_{pc}$ je RAM-instrukcija, a RAM-konfiguracija $(r_0,r_1,\dotsc,pc)$ nije završna ($pc<n_Q$) i prelazi u RAM-konfiguraciju $(r_0',r_1',\dotsc,pc')$ po programu $Q$ (odnosno njegovoj instrukciji s rednim brojem $pc$);
    \item\label{stav:P} $pc'=pc$, $I_{pc}$ je makro $P^*$, a RAM-konfiguracija $(r_0,r_1,\dotsc,ac)$ nije završna ($ac<n_P$) i prelazi u RAM-konfiguraciju $(r_0',r_1',\dotsc,ac')$ po programu $P$ (odnosno njegovoj instrukciji s rednim brojem $ac$);
    \item\label{stav:carry} $pc'=pc+1$, $I_{pc}=P^*$, RAM-konfiguracija $(r_0,r_1,\dotsc,ac)$ je završna ($ac=n_P$) i $ac'=0$.\qedhere
\end{enumerate}
\end{definicija}

Drugim riječima, makro-stroj funkcionira na dvije razine. Na "gornjoj", izvršava RAM-instrukcije u vlastitom makro-programu, koristeći vlastite registre i programski brojač baš kao RAM-stroj. Dolaskom do instrukcije $P^*$ prebacuje se na "donju" razinu, gdje izvršava RAM-instrukcije u RAM-programu $P$ koristeći \emph{iste} registre i pomoćni programski brojač. Dolaskom tog RAM-stroja $(P,(\reg{j})_{j\in\N},\textsc{ac})$ u završnu konfiguraciju, makro-stroj se vraća na "gornju" razinu: resetira \textsc{ac} na nulu, poveća \textsc{pc} za jedan, i nastavlja izvršavati vlastite instrukcije.

Vidimo da za makro-stroj postoje dva načina da radi u beskonačnoj petlji. Prvi je na gornjoj razini, gdje se svaka makro-instrukcija (barem svaka do koje programski brojač dođe) izvrši u konačno mnogo koraka (prijelaza), ali \textsc{pc} nikad ne postigne vrijednost $n_Q$. Drugi je na donjoj razini: u nekom trenutku \textsc{pc} postane $i$, i makro-stroj počne izvršavati makro $I_i=P^*$ --- no s registrima kakvi su bili u tom trenutku, izvršavanje programa $P$ nikad ne završi: \textsc{ac} nikad ne postane $n_P$, čime \textsc{pc} ostaje na istoj vrijednosti $i<n_Q$ zauvijek. Ako se pak ne dogodi nijedno od toga, makro-stroj će doći u završnu konfiguraciju $(r_0,r_1,\dotsc,n_Q,0)$, u kojoj će $r_0$ predstavljati izlazni podatak.

\begin{napomena}[{name=[svaki RAM-program je makro-program]}]\label{nap:rem}
Makro-program bez ijednog makroa jest RAM-program (konačni niz RAM-instrukcija), ali se ne izvršava na RAM-stroju, nego na makro-stroju. Ipak, definicija~\ref{def:macroconf} kaže da u tom slučaju svaka konfiguracija mora preslikavati \textsc{ac} u $0$, a definicija~\ref{def:makrolead}, točka~\ref{stav:Q}, kaže da se u tom slučaju makro-stroj ponaša isto kao i RAM-stroj. Drugim riječima, pojam $P$-izračunavanja s $\vec x$ je dobro definiran bez obzira na to na kojem stroju se izvršava. (Ovu napomenu smo mogli izbjeći tako da uopće ne definiramo RAM-stroj nego samo makro-stroj, no uvođenje pomoćnog brojača koji ništa ne "radi" i čitavo vrijeme RAM-izračunavanja stoji na $0$ djelovalo bi čudno.)
\end{napomena}

\begin{primjer}[{name=[makro-program $Q$]}]\label{pr:makro}
Uzmimo RAM-program $P_{\f{add}^3}$ iz algoritma~\eqref{eq:add3}, i promotrimo makro-stroj s programom
	%\vspace{-1em}
\begin{equation}
    Q:=\begin{prog}
        0.&\textsc{zero}\;\reg1\\
        1.&[\;]^*\\
        2.&\decr21\\
        3.&P_{\f{add}^3}^*
    \end{prog}\text.
\end{equation}
\smallskip 

\noindent Neki prijelazi između konfiguracija tog stroja su:
\begin{multline}\label{ml:Qstane}
    (0,2,4,0,\dotsc,0,0)\leadsto
    (0,1,4,0,\dotsc,0,1)\leadsto
    (0,1,4,0,\dotsc,0,0)\leadsto
    (0,0,4,0,\dotsc,0,1)\leadsto{}\\{}\leadsto
    (0,0,4,0,\dotsc,0,0)\leadsto
    (0,0,4,0,\dotsc,0,2)\leadsto
    (0,0,4,0,\dotsc,1,0)\leadsto
    (0,0,4,0,\dotsc,2,0)\leadsto{}\\{}\leadsto
    (0,0,3,0,\dotsc,3,0)\leadsto
    (0,0,3,0,\dotsc,3,3)\leadsto
    (0,0,2,0,\dotsc,3,4)\leadsto
    (1,0,2,0,\dotsc,3,5)\leadsto{}\\{}\leadsto
    (1,0,2,0,\dotsc,3,3)\leadsto
    (1,0,1,0,\dotsc,3,4)\leadsto
    (2,0,1,0,\dotsc,3,5)\leadsto
    (2,0,1,0,\dotsc,3,3)\leadsto{}\\{}\leadsto
    (2,0,0,0,\dotsc,3,4)\leadsto
    (3,0,0,0,\dotsc,3,5)\leadsto
    (3,0,0,0,\dotsc,3,3)\leadsto
    (3,0,0,0,\dotsc,3,6)\leadsto{}\\{}\leadsto
    (3,0,0,0,\dotsc,3,9)\leadsto
    (3,0,0,0,\dotsc,4,0)\lcirclearrowleft\text.
\end{multline}
Također, polazeći od "čistog" makro-stroja sa svim registrima resetiranim, imamo niz
\begin{equation}\label{eq:Q!stane}
    (0,\dotsc,0,0)\leadsto
    (0,\dotsc,0,2)\leadsto
    (0,\dotsc,1,0)\leadsto
    (0,\dotsc,2,0)\leadsto
    (0,\dotsc,1,0)\leadsto\dotsb
\end{equation}
    u kojem nijedna konfiguracija nije završna.
\end{primjer}

Sada se, jednako kao za RAM-model, može definirati \emph{makro-algoritam}, \emph{makro-iz\-ra\-ču\-na\-va\-nje}, izreka "makro-algoritam \emph{računa} funkciju" te pojam \emph{makro-izračunljive} funkcije. Na primjer, niz~\eqref{eq:Q!stane} pokazuje da $Q$-izračunavanje s $(0)$ ne stane, dok niz~\eqref{ml:Qstane} pokazuje da $Q$-izračunavanje s $(2,4)$ stane s izlaznim podatkom $3$. Također, makro-algoritam $Q^4$ računa funkciju $\f{f}:\N\times\N_+\!\times\N\times\N\to\N$, zadanu s $\f{f}(x,y,z,t):=y+z-1$.

Kao i u RAM-slučaju, uz malo više tehnikalija mogu se dokazati rezultati o determinističnosti, prebrojivosti skupa makro-izračunljivih funkcija te postojanju brojevnih funkcija koje nisu takve. Iako to predstavlja dobru vježbu, nećemo ići na taj način --- naš cilj je dobiti sve te rezultate s druge strane, tako da dokažemo da se svaki makro-stroj može \emph{simulirati} RAM-strojem, pa je skup makro-izračunljivih funkcija \emph{jednak} skupu $\mathscr Comp$ RAM-izračunljivih funkcija.

%\section{Simulacija}

%Simulaciju zapravo možemo definirati za bilo kakva dva matematička stroja --- iako će nam formalno trebati samo za makro-stroj i RAM-stroj. Osnovna ideja je da stroj $\mathcal S$ simulira stroj $\mathcal T$ ako za svaki ulaz, stroj $\mathcal S$ prolazi kroz "iste" "važne" konfiguracije kao stroj $\mathcal T$ s "istim" ulazom, istim redom, s eventualno ubačenim još nekim konfiguracijama između. Koje su konfiguracije važne je donekle subjektivno, ali završne svakako jesu važne. Također, što je potrebno da bi se dvije konfiguracije (različitih strojeva) smatrale "istima" je subjektivno, ali želimo da izlazni podatak takvih završnih konfiguracija bude isti --- ili barem izomorfan. Općenito je teško biti precizniji jer se tipovi ulaznih i izlaznih podataka te sastavni dijelovi konfiguracija, jako razlikuju na različitim strojevima, ali u konkretnom slučaju koji će nama trebati, možemo napisati preciznu definiciju.

%\begin{definicija}
%Neka je $\mathcal S$ RAM-stroj s programom $P$ te $\mathcal M$ makro-stroj s programom $Q$. Za konfiguraciju $c$ stroja $\mathcal S$ i konfiguraciju $d$ stroja $\mathcal M$ kažemo da su \emph{slične} ako se podudaraju na svim registrima, a $c$ je završna ako i samo ako je $d$ završna.

%Kažemo da $\mathcal S$ \emph{simulira} $\mathcal M$, ako za svaku mjesnost $k$, za svaki ulaz $\vec x\in\N^k$, ako je $(c_i)_{i\in\N}$ $P$-izračunavanje s $\vec x$, a $(d_j)_{j\in\N}$ $Q$-izračunavnje s $\vec x$, postoji podniz $(d_{j_i})_{i\in\N}$ (za $j_0<j_1<j_2<\dotsb$) takav da su za sve $i\in\N$, $c_i$ i $d_{j_i}$ slične.
%\end{definicija}

\subsection{Spljoštenje}

Dakle, cilj nam je opisati postupak za pretvorbu makro-strojeva u RAM-strojeve koji za iste ulaze prolaze kroz "iste" konfiguracije. One ne mogu biti doslovno iste jer makro-stroj ima dva programska brojača a RAM-stroj samo jedan, ali to je suštinski jedina razlika. Sadržaj registara makro-stroja i RAM-stroja bit će isti kako se krećemo kroz izračunavanje, i izvršavat će se iste instrukcije (istog tipa nad istim registrima) istim redom, samo će one biti u različitim programima, s različitim rednim brojevima, pa će njihova odredišta trebati biti drugačija kako bi se odnosila na odgovarajuće instrukcije u drugom programu.

Ideja konstrukcije: "spljoštimo" gornju razinu (na kojoj su makroi $P^*$) i donju razinu (na kojoj su pojedinačne instrukcije programa $P$) u jednu razinu. U računarstvu se ta tehnika zove \emph{inlining}: umjesto makro-instrukcije $P^*$\!, na isto "mjesto" (relativnu poziciju u programu u odnosu na ostale instrukcije) stavimo sve instrukcije od $P$ redom. Time su neki redni brojevi instrukcija prestali biti sinkronizirani s odredištima: prvo, svi redni brojevi instrukcija u $P$ (osim ako je makro $P^*$ bio baš na početku makro-programa), a drugo, svi redni brojevi nakon onog koji je imao makro $P^*$ (osim ako $P$ ima točno jednu instrukciju). Sve ih treba popraviti, a jednako tako i odredišta koja se na njih odnose. Precizirajmo taj postupak.

\begin{definicija}[{name=[spljoštenje]}]\label{def:flat}
Neka je $Q$ makro-program.\\ \emph{Spljoštenje} od $Q$ je RAM-program $Q^\flat$, dobiven iz $Q$ sljedećim postupkom:
\begin{quotation}
Dok god postoji barem jedan makro u $Q$:
\begin{enumerate}
    \item\label{korak:makni} makni prvi makro iz $Q$: neka je to $i.\;P^*$;
    \item\label{korak:renumeriraj} u programu $Q$, svaki redni broj veći od $i$, i svako odredište veće od $i$, povećaj za $n_P-1$ (tj.\ smanji za $1$ ako je $P$ prazan program);
    \item\label{korak:dodaj} za svaku instrukciju programa $P$, dodaj u program $Q$ instrukciju istog tipa nad istim registrom (ako ga ima), kojoj su redni broj i odredište (ako ga ima) povećani za $i$.\qedhere
\end{enumerate}
\end{quotation}
\end{definicija}

\begin{propozicija}[{name=[spljoštenje projicira $\mathscr{MP}r\mspace{-1mu}o\mspace{-2mu}g$ na $\mathscr Pr\mspace{-1mu}o\mspace{-2mu}g$]}]
	Preslikavanje ${}^\flat$ je totalna surjekcija sa skupa $\mathscr{MP}r\mspace{-1mu}o\mspace{-2mu}g$ na skup $\mathscr Pr\mspace{-1mu}o\mspace{-2mu}g$.
\end{propozicija}
\begin{proof}
Za početak trebamo vidjeti da za proizvoljni makro-program $Q$, postupak iz definicije~\ref{def:flat} uvijek stane u konačno mnogo koraka, i pritom proizvede RAM-program.

Kako je u svakom makrou $P^*$, $P$ \emph{RAM}-program, u koraku~\ref{korak:dodaj} ne dodajemo nove makroe. S druge strane, u koraku~\ref{korak:makni} uklanjamo jedan makro, a u koraku~\ref{korak:renumeriraj} ne mijenjamo broj makroa, dakle svaki prolaz kroz petlju smanjuje broj makroa za $1$. Kako svaki makro-program ima konačno mnogo makroa, postupak će sigurno završiti (nakon najviše $n_Q$ prolaza kroz petlju). A kada završi, uvjet petlje neće biti ispunjen, dakle u $Q$ više neće biti makroa: drugim riječima, pretvorili smo  $Q$ u RAM-program.

	Surjektivnost slijedi iz činjenice da je $\mathscr Ins\subset\mathscr{MI}ns$ (dakle $\mathscr Pr\mspace{-1mu}o\mspace{-2mu}g\subset\mathscr{MP}r\mspace{-1mu}o\mspace{-2mu}g$) te je ${}^\flat$ na RAM-programima identiteta: uvjet petlje već na početku nije ispunjen, pa se program uopće ne mijenja. Dakle za svaki RAM-program $P$ vrijedi $P^\flat=P$.
\end{proof}

\begin{primjer}[{name=[spljoštenje makro-programa $Q$]}]\label{pr:flat}
Spljoštimo program $Q$ iz primjera~\ref{pr:makro}. Prvi makro u $Q$ nalazi se odmah na početku ($i=0$) pa ne moramo renumerirati instrukcije koje implementiraju $\textsc{zero}\;\reg1$, već samo one ispod njih: trebamo im povećati odredišta i redne brojeve za $2-1=1$. Nakon prvog prolaza kroz petlju tako dobijemo makro-program $Q'$.

Sljedeći makro je onaj koji odgovara praznom RAM-programu, s rednim brojem $i=2$. Za njega očito ne treba provoditi korak~\ref{korak:dodaj}; samo ga uklonimo i smanjimo redne brojeve i odredišta veće od $2$ za $1$. Specijalno, to znači da u instrukciji $(3.\;\decr22)$, odredište ostaje $2$, dok se redni broj smanjuje za $1$ i postaje također $2$. Dobivamo $Q''$.

\noindent{}\begin{equation}
    Q':=\begin{prog}
    0.&\decr12\\
    1.&\goto\;0\\
    2.&[\;]^*\\
    3.&\decr22\\
    4.&P_{\f{add}^3}^*
    \end{prog}
    \qquad\qquad
    Q'':=\begin{prog}
    0.&\decr12\\
    1.&\goto\;0\\
    2.&\decr22\\
    3.&P_{\f{add}^3}^*
    \end{prog}
\end{equation}

Ostao nam je još jedan makro, ovaj put zadnja instrukcija ($i=3$). To znači da u koraku~\ref{korak:renumeriraj} ne radimo ništa, samo moramo provesti korak~\ref{korak:dodaj}. Nakon njega dobijemo
\begin{equation}\label{eq:Qflat}
    Q''':=\begin{prog}
    0.&\decr12\\
    1.&\goto\;0\\
    2.&\decr22\\
    3.&\decr16\\
    4.&\incr0\\
    5.&\goto\;3\\
    6.&\decr29\\
    7.&\incr0\\
    8.&\goto\;6\\
    9.&\decr{3}{12}\\
    10.&\incr0\\
    11.&\goto\;9\\
    \strut
    \end{prog}\qquad\begin{array}{l}
    v(0,0):=0\\
    v(0,1):=1\\
    v(0,2):=v(1,0):=v(2,0):=2\\
    v(3,0):=3\\
    v(3,1):=4\\
    v(3,2):=5\\
    v(3,3):=6\\
    v(3,4):=7\\
    v(3,5):=8\\
    v(3,6):=9\\
    v(3,7):=10\\
    v(3,8):=11\\ v(3,9):=v(4,0):=12
    \end{array}
\end{equation}
i gotovi smo: $Q'''=Q^\flat$, jer više nema makroa u programu. (Za objašnjenje funkcije $v$ čije vrijednosti su napisane pored $Q^\flat$, pogledajte skicu dokaza teorema~\ref{tm:rem}.)
\end{primjer}

Postupak za određivanje spljoštenja zapravo je neformalni algoritam, čiji je ulazni podatak makro-program, a izlazni RAM-program. Taj algoritam bismo mogli i formalizirati, tako da razvijemo kodiranja za skupove $\mathscr{MP}r\mspace{-1mu}o\mspace{-2mu}g$ i $\mathscr Pr\mspace{-1mu}o\mspace{-2mu}g$ --- no nema potrebe. Sve za što će nam trebati makro-programi je dokaz da se funkcijski programi mogu zapisati imperativno; a ta pretvorba, iako je mehanička i programabilna, je na meta-razini, "iznad" samih algoritama koji rade na prirodnim brojevima. Iako je jedan od važnih rezultata teorije izračunljivosti da se meta-algoritmi također mogu prikazati kao algoritmi, odnekud moramo početi i zadovoljiti se neformalnim objašnjenjima. 
Na ovaj postupak ćemo se vratiti u formalnom okruženju (s kodiranim RAM-programima), pri dokazu teorema o parametru (propozicija~\ref{pp:tmpar}). Tamo ćemo kodirati jedan specijalni slučaj spljoštenja, ali pokazat će se da je taj slučaj dovoljan za sve situacije u kojima nam spljoštenje formalno treba. Može se činiti cirkularnim, ali zapravo nije; baš kao ni npr.\ govor o modelu teorije skupova ZF kao o skupu --- koristimo neformalne pojmove da bismo opisali formalne.

%\subsection{Ekvivalentnost RAM-programa i makro-programa}

Kad smo već kod neformalnih objašnjenja, izrecimo i osnovni rezultat --- koji se doduše može formalno dokazati, ali je vrlo mukotrpno i zapetljano, a zapravo dokaz ne daje ništa novo ako već imamo intuiciju \emph{inlininga} kao programske tehnike.

\begin{definicija}[{name=[ekvivalentnost programa]}]\label{def:ekvprog}
Za dva (makro- ili RAM-\!) programa $P$ i $Q$ kažemo da su \emph{ekvivalentni} ako za svaku mjesnost $k\in\N_+$, algoritmi $P^k$ i $Q^k$ računaju istu funkciju.
\end{definicija}

\begin{teorem}[{name=[ekvivalentnost programa i njegova spljoštenja]}]\label{tm:rem}
Za svaki makro-program $Q$, RAM-program $Q^\flat$ je ekvivalentan s $Q$.
\end{teorem}
\begin{proof}[Skica dokaza]
Potrebno je vidjeti da funkcija iz $\N^2$ u $\N$, zadana s
	\begin{equation}\label{eq:v}
		v(pc,ac):=\bigl(\sum\nolimits_{i<pc}\begin{smallcases}n_P,&I_i\,=\,P^*\\1,&I_i\,\in\,\mathscr Ins\end{smallcases}\bigr)+ac\text{,\qquad za }pc\le n_Q\text{,\quad}ac\le\begin{smallcases}0,&I_{pc}\,\in\,\mathscr Ins\,\lor\,pc\,=\,n_Q\\n_P,&I_{pc}\,=\,P^*\end{smallcases}\text,
	\end{equation}
	ima sljedeće ključno svojstvo: svaki prijelaz između RAM-konfiguracija $\bigl(r_0,r_1,\dotsc,v(pc,ac)\bigr)$ i $\bigl(r_0',r_1',\dotsc,v(pc',ac')\bigr)$ po programu $Q^\flat$ odgovara jednom ili više prijelaza između makro-konfiguracija $(r_0,r_1,\dotsc,pc,ac)$ i $(r_0',r_1',\dotsc,pc',ac')$ po programu $Q$. Intuitivno, funkcija $v$ opisuje kako se točno transformiraju redni brojevi instrukcija pri spljoštenju, a usto i preslikava "završnu konfiguraciju programskih brojača" $(n_Q,0)$ u $n_{Q^\flat}$. Recimo, ako je $(i.\,P^*)$ prvi makro u $Q$, iz formule~\eqref{eq:v} slijedi da je $v(j,0):=j$ za sve $j<i$. Na kraju primjera~\ref{pr:flat}, u~\eqref{eq:Qflat}, navedena je funkcija $v$ za konkretni makro-program $Q$ iz primjera~\ref{pr:makro}.

Iz toga onda slijedi da se pri izvršavanju programa i njegova spljoštenja zapravo izvršavaju iste instrukcije, samo su im odredišta i redni brojevi transformirani po funkciji $v$. Dakle, semantike tih instrukcija --- promjene sadržaja registara --- iste su i odvijaju se na istim registrima, istim redom. To pak znači da ako počnemo od iste konfiguracije (početna konfiguracija s ulazom $\vec x$) što se registara tiče, registri će mijenjati svoje vrijednosti na isti način prilikom izvršavanja $Q$ i $Q^\flat$, pa će posebno i sadržaj registra $\reg0$ biti isti. Štoviše, jer je $v(n_Q,0)=n_{Q^\flat}$, $Q^\flat$-izračunavanje s $\vec x$ će stati ako i samo ako $Q$-izračunavanje s $\vec x$ stane, i tada će u $\reg0$ biti isti broj. Kako je $\vec x$ bio proizvoljan, zaključujemo da su $Q$ i $Q^\flat$ ekvivalentni.
\end{proof}

\subsection{Primjeri makroa}
Teorem~\ref{tm:rem} ima dvije važne posljedice. Prvu možemo uobličiti kao korolar.

\begin{korolar}[{name=[RAM-izračunljivost je ekvivalentna makro-izračunljivosti]}]\label{kor:rem}
Neka je $k\in\N_+$ te $\f f^k$ funkcija.

    Tada je $\f f$ RAM-izračunljiva ako i samo ako je makro-izračunljiva.
\end{korolar}
\begin{proof}
Za jedan smjer, ako je $\f f$ RAM-izračunljiva, postoji RAM-algoritam iste mjesnosti $P^k$ koji je računa.  RAM-program $P$ je i makro-program, a vidjeli smo u napomeni~\ref{nap:rem} da je svejedno izvršava li se na makro-stroju ili RAM-stroju. Drugim riječima, $P$ na makro-stroju također računa funkciju $\f f$, odnosno makro-algoritam $P^k$ računa $\f f$, pa je $\f f$ makro-izračunljiva.

Za drugi smjer, ako je $\f f$ makro-izračunljiva, postoji makro-algoritam $Q^k$ koji je računa. Po teoremu~\ref{tm:rem}, $Q^\flat$ je ekvivalentan s $Q$, dakle za svaki $k$ pa posebno i za mjesnost funkcije $\f f$, $Q^k$ i $(Q^\flat)^k$ (pišemo skraćeno $Q^{\flat k}$) računaju istu funkciju. Drugim riječima, RAM-algoritam $Q^{\flat k}$ računa funkciju $\f f$, pa je ona RAM-izračunljiva.
\end{proof}

\begin{napomena}[{name=[makroi višeg reda]}]
Druga posljedica teorema~\ref{tm:rem} je programska tehnika koja će bitno povećati izražajnost makro-programa koje pišemo. Rekli smo da je makro uvijek oblika $P^*$ gdje je $P$ \emph{RAM}-program, no zbog teorema~\ref{tm:rem} smijemo se ponašati kao da $P$ može biti i \emph{makro}-program, koji koristi već napisane makroe. Formalno, pri tome mislimo na $P^{\flat*}$\!, koji ima istu semantiku što se učinka na registre tiče.
\end{napomena}

% \subsection{Primjeri makroa}

Evo primjera korištenja te tehnike.
Prisjetimo se: za svaki $j\in\N$,
\begin{equation}
(\textsc{zero}\;\reg{j}):=\begin{prog}
0.&\decr{j}{2}\\
1.&\goto\;0
\end{prog}^*\text{
 ima semantiku $r_j'=0$.}
\end{equation}

%\subsection{Premještanja}\label{sec:move}
\noindent
Sličnom tehnikom kao za identitetu~\eqref{eq:RAMid} vidimo da za sve \emph{različite} $i,j\in\N$ makro
\begin{equation}
    (\remove{i}{j}):=\begin{prog}
    0.&\textsc{zero}\;\reg{j}\\
    1.&\decr{i}{4}\\
    2.&\incr{j}\\
    3.&\goto\;1
    \end{prog}^{\flat*}
\end{equation}
ima semantiku $r_i'=0\land r_j'=r_i$: riječima, prebacuje sadržaj $\reg{i}$ u $\reg{j}$ i pritom resetira $\reg{i}$. Ovdje je bitan uvjet $i\ne j$; pokušajte odrediti što se događa kad taj uvjet nije ispunjen. Općenito ćemo imati uvjete na "parametre" makroa pod kojima on ima traženu semantiku --- tada moramo pri svakom korištenju makroa u programu provjeriti da konkretne vrijednosti parametara zadovoljavaju te uvjete.

Evo primjera makroa s malo kompliciranijim uvjetom: neka su $i,j,n\in\N$ takvi da je $\dulj{i-j}\ge n$. Definiramo makro
\begin{equation}
    (\textsc{mmove $n$ from $\reg{i}..$ to $\reg{j}..$}):=\begin{prog}
    t.&\remove{i+t}{j+t}
    \end{prog}_{t<n}^{\flat*}
\end{equation}
sa semantikom $(\forall t<n)(r_{j+t}'=r_{i+t}\land r_{i+t}'=0)$ --- koristimo $(\forall t<n)$ kao pokratu za $(\forall t\in[0\dd n\rangle)$. Riječima, \textsc{mmove} prebacuje komad memorije duljine $n$ registara počevši od $\reg{i}$, na drugo mjesto koje počinje od $\reg{j}$, ostavljajući nule na originalnim lokacijama. Svrha korištenja te instrukcije bit će emulacija \emph{stoga} pri funkcijskim pozivima.

Moderna računala rezerviraju poseban dio svoje memorije za stog poziva (\emph{call stack}), koji se dijeli na okvire (\emph{frames}) u kojima se drže podaci o lokalnim varijablama funkcij\=a koje se trenutno izvršavaju. Pozivom funkcije, vrh stoga se pomiče, otvarajući novi okvir u kojem će se funkcija izvršavati. Povratkom iz funkcije, vrh stoga se vraća na staro mjesto, eliminirajući taj okvir tako da od njega ostane jedino povratna vrijednost.

Na RAM-arhitekturi nemamo stog poziva, ali ga možemo emulirati pomoću registara. Otvaranje okvira duljine $b$ realizirat ćemo kao pomak prvih $b$ registara za $b$ mjesta udesno (od $\reg{b}$ do uključivo $\reg{2b-1}$), a njegovo zatvaranje kao pomak u suprotnom smjeru. Osigurat ćemo da je $b$ uvijek dovoljno velik da time sačuvamo sve relevantne registre pozivatelja te da osiguramo dovoljno nul\=a na početku za sve relevantne registre pozvane funkcije --- "uvjerivši" njen program da se izvršava na zasebnom RAM-stroju.

Stvarna računala ne implementiraju stog na taj način jer je takav pristup nevjerojatno rastrošan, u prostoru (broju registara) i u vremenu (broju koraka). No kako nas zanima samo postojanje algoritama, ne i njihova složenost, taj pristup će nam biti dovoljno dobar.

%\subsection{Kopiranja}

Upravo konstruirani makroi resetiraju registre koje prenose --- što ako ih želimo sačuvati? Jedina usporedba koju imamo je ona s nulom u instrukciji tipa $\dec$, dakle jedini način da RAM-program sazna sadržaj registra je da ga dekrementira do nule. No dekrementiranjem možemo inkrementirati $1$ registar (kao u \textsc{remove}), $0$ registara (kao u \textsc{zero}), ili $2$ registra: ako su $i,j,k\in\N$ svi različiti, makro
\vspace{-1em}
\begin{equation}
    (\textsc{move}\;\reg{i}\;\textsc{to}\;\reg{j}\;\textsc{using}\;\reg{k}):=\begin{prog}
    0.&\textsc{zero}\;\reg{j}\\
    1.&\remove{i}{k}\\
    2.&\decr{k}{6}\\
    3.&\incr{i}\\
    4.&\incr{j}\\
    5.&\goto\;2
    \end{prog}^{\flat*}
\end{equation}
ima semantiku $r_j'=r_i\land r_k'=0$ (nismo napisali $r_i'$, što u skladu s našom konvencijom znači da je $r_i'=r_i$). To se dokaže po koracima, praćenjem stanja relevantnih registara kroz instrukcije:
\begin{equation}
    \begin{array}{r@{\;}l|ccc}
%\SwapAboveDisplaySkip
        & & r_i & r_j & r_k\\\hline
        0.&\textsc{zero}\;\reg{j} & r_i & 0 & r_k\\
        1.&\remove{i}{k} & 0 & 0 & r_i  \\
        2.\text{--}\mspace{1mu}5.& \text{(petlja)} &  r_i & r_i & 0
    \end{array}
\end{equation}
Naglasimo da smo za tu operaciju morali "žrtvovati" (resetirati) jedan registar sa strane.

Zbog $i\ne k$, uvjet na parametre makroa \textsc{remove} je zadovoljen.

\begin{napomena}[{name=[{terminologija makroa za kopiranje\slash premještanje registara}]}]
%Terminološki detalj: ako ste navikli na rad s modernim sustavima datoteka,
    Vjerojatno smatrate čudnim naziv \textsc{move} za ono što biste intuitivno zvali \textsc{copy} (dok se ono što biste zvali \textsc{move} ovdje zove \textsc{remove}, a ono što biste zvali \textsc{remove} ovdje se zove \textsc{zero}). Niste jedini: pogledajte recimo~\cite{url:movecopy}. Razlozi su izgubljeni u dubinama povijesti, ali moderne računalne arhitekture uglavnom terminološki prate arhitekturu \texttt{x86}, koja instrukciju za kopiranje podataka između registara (i drugih lokacija) zove \texttt{mov}. Tu terminologiju i mi slijedimo ovdje.
\end{napomena}

Svrha instrukcije \textsc{move} je prijenos argumenata: kad pri funkcijskom pozivu otvorimo novi okvir za računanje pozvane funkcije, želimo u ulazne registre staviti argumente s kojima je pozvana. Također želimo da zatvaranjem tog okvira i vraćanjem kontrole pozivatelju registri s argumentima zadrže svoje stare vrijednosti --- tako da ih pozvana funkcija može mijenjati bez straha. To je osnovna ideja \emph{prijenosa po vrijednosti}, koji koristi većina imperativnih programskih jezika niže razine (kao što je C), pa čak i moderniji jezici (Java, Ruby) kad se radi o primitivnim tipovima podataka kao što su cijeli brojevi.

Neka je $k\in\N_+$ te $j_1,j_2,\dotsc,j_k>k$ prirodni brojevi. %(ne moraju biti međusobno različiti, ali moraju biti veći od $k$).
 Definiramo makro
\begin{equation}
    (\textsc{args} \;\reg{j_1},\reg{j_2},\dotsc,\reg{j_k}):=\begin{prog} t.&\move{j_{t+1}\!}{t+1}{0}
    \end{prog}^{\flat*}_{t<k}\text,
\end{equation}
čija je semantika $(\forall t\in[1\mspace{-1mu}\dd k])(r_t'=r_{j_t})\land r_0'=0$. Uvjeti za parametre od \textsc{move} su zadovoljeni jer za svaki $t\in[1\mspace{-1mu}\dd k]$ vrijedi $0<1\le t\le k<j_t$, pa su $\reg{0}$, $\reg{t}$ i $\reg{j_t}$ različiti registri. U procesu prijenosa argumenata resetiramo izlazni registar --- što je u redu jer ionako slijedi prijenos kontrole na pozvanu funkciju, koja će tamo očekivati nulu.

\subsection{Funkcijski makro}

Napokon možemo, kako je najavljeno, definirati makro koji će nam omogućiti funkcijske pozive za bilo koju RAM-izračunljivu funkciju (za koju imamo RAM-program) na bilo kojim registrima kao argumentima, spremajući rezultat u po volji odabrani registar i čuvajući po volji velik početni komad memorije.

Prvo definiramo jedan korisni pojam. Kako svaka RAM-instrukcija djeluje na najviše jedan registar, čitav RAM-program kao konačan niz instrukcija djeluje na konačno mnogo registara. To znači da za svaki RAM-program $P$ postoji tzv\!.\ \emph{širina} --- najmanji broj $m_P\in\N$ takav da $P$ ne koristi nijedan registar $\reg{i}$ za $i\ge m_P$. Može biti i $m_P=0$, ako program uopće ne koristi registre (ako je prazan, ili se sastoji samo od instrukcija tipa \goto).

Za makro-program $Q$, možemo prirodno definirati $m_Q:=m_{Q^\flat}$ --- iako nam to zapravo neće trebati. Ali (RAM- i makro-\!) algoritmi $P^k$, pored registara koje koriste u instrukcijama, koriste i registre $\reg{1}$ do $\reg{k}$ za ulazne podatke. Moguće je da bude $m_P\le k$, ako računamo funkciju koja ne ovisi o zadnjih nekoliko argumenata. Ipak, registar $\reg{k}$ jest bitan za postupak izračunavanja te funkcije na RAM-stroju jer, iako ga ne postavlja nijedna instrukcija, postavlja ga sam rad stroja koji u početnoj konfiguraciji u njega spremi argument $x_k$. Zato definiramo širinu algoritma kao $m_{P^k}:=\max\,\{m_P,k+1\}$. Zbog $k\in\N_+$, uvijek je $m_{P^k}\ge 2$.

\begin{definicija}[{name=[funkcijski makro]}]\label{def:funmakro}
Neka je $k\in\N_+$, $\f{f}^k\in\mathscr Comp_k$ te $P_{\f{f}}^k$ RAM-algoritam koji računa $\f{f}^k$. Neka su $m,j_0,j_1,\dotsc,j_k\in\N$. Definiramo
    %\begin{equation}
	    $b:=1+\max\,\{m_{P_{\f f}}-1,m-1,k,j_0,j_1,\dotsc,j_k\}$
    %\end{equation}
te pomoću tog broja definiramo \emph{funkcijski makro}
    \vspace{-5mm}
\begin{equation}\label{mprog:funmakro}
    \bigl(P_{\f{f}}(\reg{j_1},%\reg{j_2},
    \dotsc,\reg{j_k})\to\reg{j_0}\textsc{\,using }\reg{m}..\bigr):=\begin{prog}
    0.&\textsc{mmove}\;b\;\textsc{from}\;\reg0..\;\textsc{to}\;\reg{b}..\\
    1.&\textsc{args}\;\reg{b+j_1},\reg{b+j_2},\dotsc,\reg{b+j_k}\\
    2.&P_{\f{f}}^*\\
    3.&\remove{0}{b+j_0}\\
    4.&\textsc{mmove}\;b\;\textsc{from}\;\reg{b}..\;\textsc{to}\;\reg0..
    \end{prog}^{\flat*}\text{\!\!\!\!.\!\!\!\!\qedhere}
\end{equation}
\end{definicija}

\begin{propozicija}[{name=[semantika funkcijskog makroa]}]\label{prop:semfmacro}
Semantika funkcijskog makroa, uz oznake iz definicije~\ref{def:funmakro}\\ te pokratu $\vec r:=(r_{j_1},r_{j_2},\dotsc,r_{j_k})$, opisana je sljedećim tvrdnjama:
\begin{enumerate}
    \item\label{case:in} Ako je $\vec r\in\dom{\f{f}}$, tada je $r_{j_0}'\!=\f{f}(\vec r)\land(\forall t\in[b\dd 2b\rangle)(r_t'=0)$.\\
    (Specijalno, zbog $b\ge m$, za sve $i\in[0\dd m\rangle\setminus\{j_0\}$ vrijedi $r_i'=r_i$.)
    \item\label{case:notin} Ako $\vec r\notin\dom{\f{f}}$, izvršavanje funkcijskog makroa ne stane.
\end{enumerate}
\end{propozicija}
\begin{proof}
Prvo dokažimo da su zadovoljeni svi uvjeti na parametre korištenih makroa: za prvu i zadnju instrukciju to je $\dulj{b-0}=\dulj{0-b}=b\ge b$, za prijenos argumenata je $b+j_t\ge b>k$, a za prijenos povratne vrijednosti je $b+j_0\ge b\ge 1>0$.

Za tvrdnju~\ref{case:in}, pogledajmo redom učinke pojedinih makro-instrukcija iz definicije~\ref{def:funmakro}.

	Nakon prve instrukcije tipa \textsc{mmove}, prvih $b$ registara bit će resetirano, a njihove stare vrijednosti $r_0,r_1,\dots,r_{b-1}$ bit će u bloku $\mathcal B$ koji se sastoji od idućih $b$ registara. Posebno, u $\reg{b+j_t}\!$ nalazit će se $r_{j_t}$, za sve $t\in[1\mspace{-1mu}\dd k]$.

Dakle, instrukcija \textsc{args} će u ulazne registre $\reg1,\dots,\reg{k}$ zapisati upravo vrijednosti $\vec r$. Ostale registre neće mijenjati, pa će $\reg0$ i dalje biti resetiran, kao i svi registri $\reg{i},i\in\langle k\dd b\rangle$, a u $\mathcal B$ će i dalje biti "\!\emph{backup}".

	Sada slijedi izvršavanje makroa $P_{\f{f}}^*$, odnosno RAM-programa $P_{\f{f}}$ na trenutnom stanju registara. Kako je to RAM-program, po napomeni~\ref{nap:rem} slijedi da će imati isti učinak na registre kao da se izvršava na RAM-stroju, a iz $b\ge m_{P_{\f{f}}^k}$ i prethodnog odlomka slijedi da će njegovo izvršavanje biti isto kao da se izvršava na RAM-stroju u početnoj konfiguraciji (i neće promijeniti sadržaj bloka $\mathcal B$). Kako $P_{\f{f}}^k$ računa funkciju $\f{f}$, a u "početnoj" konfiguraciji mu se u ulaznim registrima nalazi $\vec r\in\dom{\f{f}}$, slijedi da će izvršavanje tog makroa  (zapravo $P_{\f{f}}$-izračunavanje s $\vec r$) stati, i u "završnoj" konfiguraciji sadržaj registra $\reg0$ će biti $\f{f}(\vec r)$.

	Nakon toga izvršavanje funkcijskog makroa prijeći će na instrukciju tipa \textsc{remove}, koja će tu vrijednost $\f{f}(\vec r)$ zapisati u registar $\reg{b+j_0}$, koji se nalazi u $\mathcal B$ zbog $j_0<b$. Svi ostali registri iz $\mathcal B$ i dalje će sadržavati \emph{backup} početnih vrijednosti prvih $b$ registara. Ne znamo što će biti u prvih $b$ registara (osim što će $\reg0$ biti resetiran) jer to ovisi o konkretnom programu $P_{\f f}$, ali zapravo to nije ni bitno.

Naime, zadnja instrukcija tipa \textsc{mmove} će čitav taj blok prepisati \emph{backup}-blokom $\mathcal B$, vrativši prvih $b$ registara na originalne vrijednosti (konkretno, zanimat će nas da se sačuva prvih $m\le b$ registara), osim što će u $\reg{j_0}$ pisati vraćena vrijednost iz $\reg{b+j_0}$, dakle $\f f(\vec r)$. $\mathcal B$ će time biti resetiran. To sve možemo prikazati tablicom:
\begin{equation}\label{eq:funmakrotab}
    \begin{array}{r@{\;}l|cr@{,\dotsc,\,}lc|ccc|}
%\SwapAboveDisplaySkip
      &                                                             & r_0          & r_1     & r_k     & r_{j_0}      & r_b & r_{b+j_0}    & r_{2b-1}\\\hline
0.&\textsc{mmove}\;b\;\textsc{from}\;\reg0..\;\textsc{to}\;\reg{b}..& 0            & 0       & 0       & 0            & r_0 & r_{j_0}      & r_{b-1} \\
1.&\textsc{args}\;\reg{b+j_1},\reg{b+j_2},\dotsc,\reg{b+j_k}        & 0            & r_{j_1} & r_{j_k} & 0            & r_0 & r_{j_0}      & r_{b-1} \\
2.&P_{\f{f}}^*                                                        & \f{f}(\vec r) & ?       & ?       & ?            & r_0 & r_{j_0}      & r_{b-1} \\
3.&\remove{0}{b+j_0}                                                & 0            & ?       & ?       & ?            & r_0 & \f f(\vec r) & r_{b-1}\\
4.&\textsc{mmove}\;b\;\textsc{from}\;\reg{b}..\;\textsc{to}\;\reg0..& r_0          & r_1     & r_k     & \f f(\vec r) & 0   & 0            & 0
    \end{array}\,\text.
\end{equation}
Tablica nije dovoljno precizna za sve mogućnosti: recimo, može biti $j_0=1$ ako želimo promijeniti $\reg{1}$ \emph{in-place}. No zajedno s tekstnim opisom, tablica pruža dobar uvid u sve što se zbiva pri izvršavanju funkcijskog makroa.

	Za tvrdnju~\ref{case:notin}, svo zaključivanje izgleda isto do trenutka kada moramo zaključiti $\vec r\in\dom{\f{f}}$. No u ovom slučaju to ne vrijedi, pa po definiciji računanja funkcije, $P_{\f{f}}$-izračunavanje s~$\vec r$ neće stati. To pak znači da rad makro-stroja, koji izvršava funkcijski makro, neće stati (zapet će u beskonačnoj petlji "na donjoj razini", izvršavajući instrukciju $2.\,P_{\f f}^*$). Prema skici dokaza teorema~\ref{tm:rem}, neće stati ni RAM-stroj koji izvršava spljoštenje tog makroa, što smo trebali dokazati.
\end{proof}

Definicijom funkcijskog makroa pripremili smo teren za drugačiji model iz\-ra\-čun\-lji\-vo\-sti: \emph{funkcijsku} paradigmu --- gdje je bitno teže vizualizirati strojeve, algoritme, konfiguracije i izračunavanja, ali je zato mnogo lakše dokazati da su pojedine konkretne funkcije izračunljive (pokušajte primjerice dokazati da je skup $\mathbb P$ RAM-izračunljiv pisanjem RAM-programa za $\chi_{\mathbb P}^1$). Dokazom ekvivalentnosti tih dvaju modela imat ćemo onda najbolje od oba svijeta.