turing.tex

\chapter{Turing-izračunljivost}\label{ch:Turing}

%\section{Zašto nam treba još jedan model?}

Uveli smo dva modela izračunljivosti brojevnih funkcija --- RAM-izračunljivost i parcijalnu rekurzivnost --- i dokazali da su ekvivalentni, usprkos bitno različitim pristupima (imperativnom odnosno funkcijskom) definiciji algoritma. To je dobar argument za Church--\!Turingovu tezu, da su izračunljive funkcije iste u svim modelima --- odnosno u modernijem obliku, da su sve programske paradigme jednako snažne. Ipak, pritom su zanemarena dva aspekta izračunljivosti.

% \subsection{Elementarne operacije}

Prvi je izračunljivost funkcija koje nisu brojevne. Rekli smo u uvodnom poglavlju, i opravdali to mnogo puta kasnije --- skup $\N$ je idealan za matematički tretman izračunljivosti, ali nije baš vjeran onom što se događa u praksi. Osnovna razlika je u konačnosti odnosno beskonačnosti skupova relevantnih za izračunavanje.

Primjerice, u RAM-modelu, skup mogućih stanja pojedinog registra je beskonačan. Često je problematično shvaćanje beskonačnosti kao "jako mnogo, pa još malo više". Zapravo, bliže definiciji beskonačnosti bilo bi "jako mnogo, pa onda još beskonačno više" --- ma koliko velik konačni skup uzeli od beskonačnog skupa, ostatak je jednako velik kao da nismo uzeli ništa.

Konkretno, lako se zavarati primjerima u kojima u RAM-registrima stoje brojevi poput $0$, $150$ ili $2^{257}$, i misliti da su RAM-registri nešto kao obični procesorski registri, samo "malo veći". Kodiranje pokazuje koliko je to daleko od istine: u RAM-registar možemo staviti i brojeve poput broja $e_0$ iz primjera~\ref{pr:Qflatkod}, koji ima $579\,690\,725\,279$ \emph{znamenaka}! Štoviše, takva procedura nije ništa neuobičajeno; ona odgovara prirodnom postupku računanja $\f{univ}(\kr{2,4},e_0)$, odnosno konstrukciji rezultata $Q^\flat$-izračunavanja s $(2,4)$, na univerzalnom RAM-stroju (dobivenom kompiliranjem simboličke definicije funkcije $\f{univ}$).

Stvarna računala, naravno, takve složene strukture (zamislimo $e_0$ kao \emph{bytecode}, neku vrstu strojnog koda) ne kodiraju pomoću prirodnih brojeva, već preko nizova bitova, bajtova ili većih procesorskih \emph{riječi}. Ključno je da je skup $\Gamma$ svih stanja pravog procesorskog registra \emph{konačan}. Način na koji se onda reprezentira potencijalna beskonačnost ulaznih podataka (što moramo, jer jedino beskonačni skupovi imaju netrivijalnu teoriju izračunljivosti), kao i međurezultata u izračunavanju, je kroz neograničenost same memorije, odnosno broja memorijskih ćelija koje sadrže po jedan element iz $\Gamma$.

I ovdje vrijedi univerzalni princip da na konačnim skupovima možemo dopustiti bilo kakve transformacije kao elementarne korake, reprezentirajući ih tablicama --- dok s beskonačnim skupovima moramo biti oprezni, ograničavajući transformacije samo na one izračunljive. Kako su ti beskonačni skupovi u pravilu trivijalno izomorfni s $\N$, kao osnovne korake dopuštamo samo prijelaz na sljedeći odnosno prethodni (ako već nije~$0$) prirodni broj.

Zato smo na konfiguracijama RAM-stroja dozvoljavali samo one prijelaze kod kojih se stanje pojedinog registra mijenja za najviše $1$ u svakom koraku; dok smo za stanje programskog brojača dozvoljavali skokove na proizvoljnu legalnu vrijednost --- upravo jer legalnih vrijednosti programskog brojača za fiksni RAM-stroj ima konačno mnogo. Također, osnovna ideja od koje dolazi i ime RAM-stroja, \emph{random access}, znači da njegova "memorijska sabirnica" može adresirati proizvoljni registar u jednom koraku --- što možemo upravo jer adres\=a relevantnih registara za fiksni RAM-algoritam ima konačno mnogo.

Ako želimo beskonačnost prikazati ne kroz veličinu sadržaja pojedinog registra nego kroz broj ćelija potrebnih da se zapiše podatak, zapravo imamo "transponirani" model: na pojedinoj ćeliji (jednom kad dođemo do nje) ćemo moći napraviti proizvoljnu transformaciju u jednom koraku, jer je skup $\Gamma$ mogućih stanja pojedine ćelije konačan --- ali pristup do pojedine ćelije više neće moći biti \emph{random access}, već ćemo u jednom koraku samo moći adresu trenutno promatrane ćelije povećati ili smanjiti (ako nije $0$) za jedan. To je \emph{jezični model} izračunavanja, tako nazvan jer odgovara onom kako (barem zapadni) jezici funkcioniraju: od konačnog broja slova u abecedi nizanjem možemo dobiti proizvoljno komplicirane riječi, rečenice i tekstove. Da bismo povećali izražajnost, ne uvodimo nova slova, već pišemo dulje rečenice.

Možda ovdje treba objasniti kako moderna računala postižu \emph{random access} i na potencijalno neograničenoj memoriji. Objašnjenje je jednostavno: varaju. Njihova memorija \emph{nije} potencijalno neograničena, jer ovisi o veličini adresnog prostora. Jedno $64$-bitno računalo, koliko god mu virtualne memorije dali, ne može adresirati više od $2^{64}$ bajtova. To varanje u stvarnom svijetu prolazi jer s trenutnom tehnologijom ne možemo uopće sastaviti funkcionalnu memoriju od $2^{64}$ bajtova (što je više od osamnaest milijuna terabajta), ali za $32$-bitna računala to ograničenje (na $4\,GiB$) je bilo vrlo stvarno i nezgodno, i uostalom jedan od glavnih razloga za prijelaz na $64$-bitnu arhitekturu.

Sličan primjer koji je nedavno došao do granice svojih mogućnosti je internetski protokol IPv4, ilustrativan jer daje uvid u to kako se takvi problemi mogu riješiti iteriranjem adresiranja: NAT (\emph{Network Address Translation}) pokazuje da ako se u jednom koraku (DNS) može adresirati $t=2^{32}$ računala, u dva se koraka (DNS + \emph{router}) može u idealnom slučaju adresirati $t^2=2^{64}$ računala. Više nam vjerojatno neće nikada trebati jer ćemo u međuvremenu prijeći na IPv6, ali u $n$ koraka mogli bismo adresirati $t^n$ računala, zamišljajući generaliziranu IP-adresu kao $n$-znamenkasti broj u bazi $t$ --- ili $32n$-znamenkasti broj u bazi $2$. Jedina razlika kod jezičnog modela je u tome što umjesto binarnog zapisa adrese korisimo unarni, u kojem su elementarne operacije samo inkrement i dekrement (koji ostavlja nulu fiksnom).

Iako je unarni zapis eksponencijalno lošiji od binarnog (i svih ostalih pozicijskih) zapisa --- broj koji u bazama $2$, $3$, $4$,~\ldots\ ima nekoliko desetaka znamenaka, zapisan unarno može imati milijarde milijardi milijardi~\ldots\ "znamenaka" --- opet, to je samo razlika u složenosti, odnosno u performansama algoritma, ne u samom postojanju algoritma, i kao takva neće nam biti važna. Ono što nam jest važno je da u jezičnom modelu adresiranje pojedine ćelije zahtijeva netrivijalne algoritme, a bilo kakva promjena sadržaja ćelije je elementarna operacija --- upravo suprotno od RAM-modela.

%\subsection{Računanje bez računala}

Drugi aspekt koji smo u potpunosti zanemarili u brojevnom modelu je povijesni. Danas, kad smo na svakom koraku okruženi računalima, a većina n\=as jedno nosi u džepu, lako je zaboraviti da računala ne postoje oduvijek. Zapravo, u upotrebljivom obliku postoje tek nekoliko desetaka godina. S druge strane, algoritmi postoje već milenijima: Euklidov algoritam nastao je prije modernog brojenja godina, a neki babilonski algoritmi potječu sa samih početaka pisane povijesti. Od kakve je koristi algoritam ako nema računala na kojem se može izvršavati?

Naravno, algoritme su izvršavali ljudi. Iako ljudski mozak po svojoj prirodi nije savršen supstrat za doslovno slijeđenje instrukcija kroz višeznamenkaste brojeve koraka, moderno obrazovanje svjedoči da se može tome na\-u\-či\-ti. Doista, rješavanje većine školskih matematičkih zadataka se može svesti na provođenje nekog algoritma. Mnoge takve zadatke računala rješavaju brže i točnije od ljudi, što se vidi kroz uspjeh aplikacija kao što je \texttt{photomath}. Iako su ljudi bolji u pronalaženju (logičkih, analogijskih ili asocijativnih) veza među pojmovima, potreba za rješavanjem problema iz stvarnog života koji se mogu precizno klasificirati uvjetovala je pronalazak mnogih algoritama daleko prije izuma računala. Motivacija je uvijek bila ista: optimizacija i specijalizacija ljudskog rada. Jedan čovjek može osmisliti algoritam, koji poslije milijuni ljudi mogu provoditi i tako rješavati stvarne probleme, ne razumijevajući nužno zašto algoritam funkcionira. No da bi to uspjelo, koraci algoritma moraju biti takvi da njegovo provođenje ne zahtijeva nikakav angažman pored onog specificiranog algoritmom --- niti ikakvo vanjsko znanje osim poznavanja ulaznih podataka, i nekoliko elementarnih vještina za koje smatramo da su svojstvene svim radno sposobnim ljudima: čitanje i pisanje simbola iz fiksnog konačnog skupa te odlučivanje na osnovi pročitanog.

Britanski matematičar Alan Mathison Turing prvi je uspješno formalizirao taj koncept. U svom članku~\cite{turing}, prije više od 80 godina i svakako prije nastanka digitalnih elektroničkih računala, Turing govori o ljudima koji računaju decimale nekih konkretno zadanih realnih brojeva --- za što danas znamo da je vrlo slično računanju vrijednosti nekih konkretno zadanih brojevnih funkcija. Iako je i prije tog članka bilo pokušaja formalizacije algoritma, Turingov se ističe po tome što detaljno motivira svoje definicije, koristeći tada poznate činjenice vezane uz ljudsku percepciju i kogniciju. Čovjekov fizički rad za vrijeme provođenja algoritma, i misaona stanja kroz koja prolazi, nisu samo incidentni dio opisa algoritma --- oni su u tom članku suštinski ugrađeni u definiciju. Tako možemo biti sigurni da doista modeliramo ono što se događa u stvarnom svijetu kad čovjek provodi algoritam, a ne matematičku apstrakciju kao što je primjerice $\lambda$-račun.

%\subsection{Turingov stroj}

Ako modeliramo ljude, odakle onda Turingovi \emph{strojevi}? Turing je bio svjestan fenomena da je lako pomisliti kako opisujemo postupak koji ne zahtijeva nikakvo eksterno znanje, a da to zapravo nije istina. Razumijevanje napisanog ili izgovorenog jezika, prepoznavanje objekata na slikama, pa čak i osnove socijalnog ponašanja, vještine su koje smo toliko duboko internalizirali da nam se čine elementarnima --- a zapravo pretpostavljaju ogromne količine znanja o svijetu koji nas okružuje. Jednostavni primjer: rečenice hrvatskog jezika "Ana i Marija su sestre."\ i "Ana i Marija su majke."\ imaju potpuno istu sintaksnu strukturu, ali fundamentalno različitu semantiku, za čiju je konstrukciju potrebno netrivijalno znanje o ljudskoj biologiji (mogu biti sestre jedna drugoj, ali ne mogu biti majke jedna drugoj) --- a ipak nam se svaka od te dvije semantike nametne sasvim prirodno čitajući odgovarajuću rečenicu, i uopće ne razmišljamo kako bi moglo biti drugačije, sve dok ih ne vidimo jednu pored druge.

Da bi svoje čitatelje uvjerio kako njegove elementarne operacije doista ne zahtijevaju nikakvo implicitno pretpostavljeno znanje, Turing je paralelno opisao i zamišljeni, idealizirani, \emph{stroj} koji može provoditi te operacije. Taj stroj, odnosno njegovu matematičku formalizaciju (neki detalji su kasnije promijenjeni radi lakšeg razumijevanja) danas nazivamo Turingovim strojem. Ipak, treba razumjeti da "ove operacije su toliko elementarne da bi ih mogao provoditi i mehanički stroj" nije poziv na konstrukciju stvarnog stroja, već apel na intuiciju da smo osnovni opis algoritma lišili svega suvišnog.

%\section{Osnovni pojmovi i primjer Turing-izračunavanja}
\section{Izračunljivost jezičnih funkcija}\label{sec:tikp}

U literaturi postoje brojne varijante Turingova stroja --- mi slijedimo~\cite{sipser}, uz male modifikacije kako bismo lakše dokazivali teoreme. Za početak ponovimo definicije.

Ulazna abeceda, ili samo \emph{abeceda}, je konačan neprazan skup. Obično je označavamo sa $\Sigma$ i smatramo fiksnom. Njene elemente zovemo \emph{znakovima} --- ne\-od\-re\-đe\-ne znakove (znakovne varijable) pišemo malim grčkim slovima s početka alfabeta ($\alpha$, $\beta$, $\gamma$), dok konkretne znakove pišemo u fontu fiksne širine: $\t a$, $\t b$, $\t 0$, $\t 1$. \emph{Riječ} (nad $\Sigma$) je bilo koji konačan niz znakova, najčešće označen slovom $w$, $v$ ili $u$. Riječi pišemo konkatenacijom (nizanjem) znakova: recimo, riječ $(\t0,\t1,\t1)$ pišemo kao $\t{011}$. Dakle, skup svih riječi je skup $\Sigma^*$ svih konačnih nizova znakova. Duljinu riječi $w$ označavamo s $\dulj{w}$. Prazni niz (duljine $0$) zovemo \emph{praznom riječju} i označavamo s $\varepsilon$. \emph{Jezik} (nad $\Sigma$) je bilo koji podskup od $\Sigma^*$. \emph{Jezična funkcija} (nad $\Sigma$) je bilo koja parcijalna funkcija $\varphi:\Sigma^*\rightharpoonup\Sigma^*$.

\begin{napomena}[{name=[abeceda je dio identiteta jezične funkcije]}]
Kao i mjesnost kod brojevnih funkcija i relacija, tako i abecedu kod jezika i jezičnih funkcija smatramo dijelom njihova identiteta; preslikavanje nad $\{\t a,\t b\}$ koje riječi pridružuje njen reverz (obrnuto čitanu riječ), različito je od preslikavanja nad $\{\t a,\t c\}$ zadanog istim pravilom. Ili, jezik svih riječi koje se sastoje samo od znakova $\t a$ i $\t b$ je različit kao jezik nad $\{\t a,\t b,\t c\}$ i kao jezik nad $\{\t a,\t b,\t d\}$ --- iako se u ovom slučaju radi o skupu s istim elementima. Motivacija je slična kao u slučaju praznih relacija: komplementi su različiti, a i karakteristične funkcije tih jezika su različite (jer imaju različite domene).
\end{napomena}

\begin{definicija}[{name=[Turingov stroj]}]
Neka je $\Sigma$ abeceda. \emph{Turingov stroj} (nad $\Sigma$) je matematički (idealizirani) stroj, obično zapisan kao uređena sedmorka $\mathcal T=(Q,\Sigma,\Gamma,\bl,\delta,q_0,q_z)$, koji sadrži:
\begin{itemize}
\item konačnu \emph{radnu abecedu} $\mspace{1mu}\Gamma\supset\Sigma$, s istaknutim elementom $\bl\in\Gamma\setminus\Sigma$ (\emph{praznina});
    \item konačni skup \emph{stanja} $Q$, s elementima $q_0\in Q$ (\emph{početno} stanje) i $q_z\in Q$ (\emph{završno} stanje);
    \item konačnu \emph{funkciju prijelaza} $\delta:(Q\setminus\{q_z\})\times\Gamma\to Q\times\Gamma\times\{-1,1\}$.\qedhere
\end{itemize}
\end{definicija}

Umjesto registara, Turingov stroj ima \emph{ćelije} (također adresirane prirodnim brojevima), svaka od kojih u svakom trenutku izračunavanja sadrži proizvoljni element od $\Gamma$. Kao što su kod RAM-stroja na početku izračunavanja svi registri osim ulaznih bili inicijalizirani na $0$, tako će kod Turingova stroja sve ćelije osim ulaznih biti inicijalizirane na $\bl$. Po analogiji s $\N_+=\N\setminus\{0\}$ označimo $\Gamma_+:=\Gamma\setminus\{\bl\}$.

\begin{definicija}[{name=[Turing-konfiguracije i prijelazi među njima]}]
	Neka je $\mathcal T=(Q,\Sigma,\Gamma,\bl,\delta,q_0,q_z)$ Turingov stroj. \emph{Konfiguracija} od $\mathcal T$ je bilo koja uređena trojka $(q,n,t)\in Q\times\N\times\Gamma^\N$, takva da je niz $t$ skoro svuda $\bl$ (odnosno, $t^{-\mspace{-2mu}1}[\Gamma_+]$ je konačan skup). Komponente konfiguracije zovu se redom \emph{stanje}, \emph{pozicija} i \emph{traka}. Konfiguracija je \emph{završna} ako joj je stanje završno ($q_z$). \emph{Početna konfiguracija} s ulazom $w=\alpha_0\alpha_1\dotsm\alpha_{\dulj{w}-1}\in\Sigma^*$ je trojka $(q_0,0,w\bl\ldots)$, čija je traka definirana s $(w\bl\ldots)_i:=(\text{$\alpha_i$ ako je $i<\dulj w$, a inače $\bl$})$.%\begin{smallcases}
%\alpha_i,&i<\dulj{w}\\
%\,\bl\,,&\text{inače}
%\end{smallcases}$.

	Za konfiguracije $c=(q,n,t)$ i $d=(q',n',t')$ Turingova stroja $\mathcal T$ kažemo da $c$ \emph{prelazi} u $d$, pišući $c\leadsto d$, ako je $c$ završna i $c=d$ (pišemo $c\!\lcirclearrowleft$), ili uz oznake $\delta(q,t_n)=:(p,\beta,d)$ vrijedi $q'=p$, $n'=\max\,\{n+d,0\}$, $t'_n=\beta$ te $t'_i=t_i$ za sve $i\in\N\setminus\{n\}$.
\end{definicija}

Traku možemo zamisliti kao s jedne strane ograničen, a s druge strane neograničen, niz ćelija, u kojem su od nekog mjesta nadalje samo prazne ćelije (one u kojima piše praznina). Ulaz za Turingov stroj je riječ nad $\Sigma$, koja se na početku izračunavanja zapiše na lijevi kraj trake redom (ostatak trake je prazan). U svakom koraku, funkcija prijelaza trenutno stanje i sadržaj trenutne ćelije preslikava u novo stanje, novi znak trenutne ćelije te pomak ulijevo ili udesno na susjednu ćeliju, koja time postaje trenutna u idućem koraku (pomak ulijevo od početne ćelije rezultira ostajanjem na mjestu). To se događa dok konfiguracija ne postane završna, i tada, ako je traka oblika $v\bl\ldots$ za neku riječ $v\in\Sigma^*$, kažemo da je $v$ izlaz Turingova stroja s ulazom $w$.

\begin{lema}[{name=[determinističnost Turingovih strojeva]}]\label{lm:Turingdet}
Svaka konfiguracija Turingova stroja prelazi u točno jednu konfiguraciju.% tog stroja.
\end{lema}
\begin{proof}
	Neka je $\mathcal T$ Turingov stroj te $c=(q,n,t)$ proizvoljna njegova konfiguracija. Ako je $q=q_z$, tada $c\leadsto c$, i ni u koju drugu konfiguraciju jer $\delta$ nije definirana u $(q_z,t_n)$. Ako pak $c$ nije završna, postoje jedinstveni $p$, $\beta$ i $d$ takvi da je $\delta(q,t_n)=(p,\beta,d)$, koji jednoznačno (zajedno s $q$, $n$ i $t$) određuju $q':=p$, $n':=\max\,\{n+d,0\}$ i niz $t':=\bigl(\begin{smallcases}\beta,&j=n\\t(j),&\text{inače}\end{smallcases}\!\bigl)_{j\in\N}$ takve da $c\leadsto(q',n',t')$.
\end{proof}

\begin{definicija}[{name=[Turing-izračunljiva jezična funkcija]}]\label{def:Tcomputefi}
Neka je $\Sigma$ abeceda, neka je $w\in\Sigma^*$ riječ te neka je $\mathcal T$ Turingov stroj nad~$\Sigma$. \emph{$\mathcal T$\!-izračunavanje s $w$} je niz $(c_n)_{n\in\N}$ konfiguracija od $\mathcal T$, takav da je $c_0$ početna konfiguracija s ulazom $w$, a za svaki $i\in\N$, $c_i\leadsto c_{i+1}$. Kažemo da to izračunavanje \emph{stane} ako postoji $n_0\in\N$ takav da je $c_{n_0}$ završna konfiguracija.

Neka je $\varphi$ jezična funkcija nad $\Sigma$. Kažemo da $\mathcal T$ \emph{\!računa} $\varphi$ ako za sve $w\in\Sigma^*$ vrijedi:
\begin{itemize}
    \item Ako je $w\in\dom\varphi$, tada $\mathcal T$\!-izračunavanje s $w$ stane i završna konfiguracija mu je oblika $\bigl(q_z,n,\varphi(w)\bl\ldots\bigr)$ za neki $n\in\N$ (pozicija nije bitna).
    \item Ako $w\notin\dom\varphi$, tada $\mathcal T$\!-izračunavanje s $w$ ne stane.
\end{itemize}
Jezična funkcija $\varphi$ je \emph{Turing-izračunljiva} ako postoji Turingov stroj koji je računa.
\end{definicija}

Kao i za RAM-model, mogli bismo dokazati da za svaki Turingov stroj $\mathcal T$ i njegov ulaz $w$ postoji jedinstveno $\mathcal T$\!-izračunavanje s $w$, ali ne i da svaki Turingov stroj računa neku jezičnu funkciju. Traka u završnoj konfiguraciji ne mora biti oblika $v\bl\ldots$ za $v\in\Sigma^*$: može sadržavati znakove iz $\Gamma_+\!\setminus\Sigma$, ili sadržavati neki znak iz $\Sigma$ nakon prve praznine. Za takve "patološke" Turingove strojeve nećemo reći da računaju ikakvu funkciju --- zapravo ih nećemo uopće promatrati, ali ako želimo iskazati neku tvrdnju univerzalno po svim Turingovim strojevima, dobro je imati na umu da i takvi postoje.

%\subsection{Primjer Turing-izračunavanja}

\begin{primjer}[{name=[funkcija koja riječi parne duljine preslikava u prvu polovicu]}]\label{pr:pola}
Nad $\Sigma:=\{\t a,\t b\}$ promotrimo funkciju $\varphi_h:\Sigma^*\rightharpoonup\Sigma^*$, čija je domena skup svih riječi parne duljine, a $\varphi_h(\alpha_1\alpha_2\dotsm\alpha_{2k}):=\alpha_1\alpha_2\dotsm\alpha_k$ (prva polovica riječi).
	
	Primjerice, za $w_1:=\t{aababa}$ vrijedi $\dulj{w_1}=6$, pa je $w_1\in\dom{\varphi_h}$\! te $\varphi_h(w_1)=\t{aab}$.

	S druge strane, za $w_2:=\t{bbb}$ vrijedi $\dulj{w_2}=3$, pa $w_2\notin\dom{\varphi_h}$.

Funkcija $\varphi_h$ je Turing-izračunljiva: računa je Turingov stroj
\begin{equation}
    \mathcal T_h:=(\{\textsc a,\textsc b,\textsc c,\textsc d,\textsc e,\textsc f\},\Sigma,\{\bl,\t a,\t b,\t c,\t d\},\bl,\delta_h,\textsc a,\textsc e)\text,
\end{equation}
čija je funkcija prijelaza (kao konačna funkcija) zadana tablicom
\begin{equation}\label{eq:deltapola}
\begin{array}{c|ccccc}
    \delta_h &\bl               &\t a               &\t b               &\t c               &\t d               \\\hline
    \textsc a&(\textsc e,\bl,+1)&(\textsc b,\t c,+1)&(\textsc b,\t d,+1)&(\textsc f,\t c,-1)&(\textsc f,\t d,-1)\\
    \textsc b&(\textsc c,\bl,-1)&(\textsc b,\t a,+1)&(\textsc b,\t b,+1)&(\textsc f,\t c,-1)&(\textsc f,\t d,-1)\\
    \textsc c&(\textsc f,\bl,-1)&(\textsc d,\bl ,-1)&(\textsc d,\bl ,-1)&(\textsc f,\t c,-1)&(\textsc f,\t d,-1)\\
    \textsc d&(\textsc f,\bl,-1)&(\textsc d,\t a,-1)&(\textsc d,\t b,-1)&(\textsc a,\t a,+1)&(\textsc a,\t b,+1)\\
    \textsc f&(\textsc f,\bl,-1)&(\textsc f,\t a,-1)&(\textsc f,\t b,-1)&(\textsc f,\t c,-1)&(\textsc f,\t d,-1)
\end{array}\text.
\end{equation}
Kao što vidimo, takav način zadavanja Turingova stroja nije naročito čitljiv --- zato se obično crtaju dijagrami. Recimo, $\mathcal T_h$ bismo mogli prikazati dijagramom
\begin{equation}
\begin{tikzpicture}[baseline=(D)]\label{dia:Th}
\node[state,initial] (A) {$\textsc a$};
\node[state,right of=A] (B) {$\textsc b$};
\node[state,below of=B] (C) {$\textsc c$};
\node[state,left of=C] (D) {$\textsc d$};
\node[state,accepting,above left of=D] (E) {$\textsc e$};
\draw
(A) edge[below] node{\bl} (E)
(A) edge node[above]{\t a:\t c} node[below]{\t b:\t d} (B)
(B) edge[loop right] node{$\Sigma$} (B)
(B) edge[dashed,right] node{\bl} (C)
(C) edge[dashed] node[above]{\t a:\bl} node[below]{\t b:\bl} (D)
(D) edge[right] node[align=center]{\t c:\t a\\\t d:\t b} (A)
(D) edge[dashed,loop left] node{$\Sigma$} (D)
;
\end{tikzpicture}\text.
\end{equation}
Recimo ponešto o konvencijama pri crtanju takvih dijagrama. Crtamo konačni usmjereni graf, čiji su vrhovi stanja, a bridovi su prijelazi. Opće pravilo je da se prijelaz $\delta(p,\alpha)=(q,\beta,d)$ prikazuje kao strelica od vrha $p$ prema vrhu $q$, na kojoj piše $\alpha\mathord:\beta$. Strelicu crtamo kao punu ako je $d=1$ (pomak udesno), a kao iscrtkanu ako je $d=-1$ (pomak ulijevo).

Više prijelaza s istim $p$, $q$ i $d$ prikazujemo strelicom s više oznaka $\alpha_1\mathord:\beta_1,\dotsc,\alpha_k\mathord:\beta_k$. Ako se znak ne mijenja ($\alpha=\beta$), umjesto $\alpha\!:\!\alpha$ pišemo samo $\alpha$. Oznaku za skup $S\subseteq\Gamma$ možemo napisati na brid umjesto pojedinih elemenata (kao što smo na dijagramu učinili sa $\Sigma$).

    Početno stanje označavamo "strelicom niotkud" --- kako je na dijagramu označeno stanje $\textsc a$. Završno stanje označavamo dvostrukim krugom --- kako je na dijagramu označeno stanje $\textsc e$. I još jedno pravilo koje bitno povećava preglednost dijagrama: ne pišemo stanja ni prijelaze koji više ne mogu voditi do završnog stanja. Običaj je prilikom konstrukcije Turingova stroja imati jedno stanje $q_x$ (za $\mathcal T_h$ to je $\textsc f$), takvo da $\delta$ svaku "nemoguću situaciju" $(q,\alpha)$ preslika u $(q_x,\alpha,-1)$. Specijalno to vrijedi i za $q=q_x$ (za sve $\alpha\in\Gamma$) pa Turingov stroj, ako se ikad nađe u nekoj od tih nedozvoljenih konfiguracija, više nikada neće stati.

    Efektivno, to je "stanje greške" koje ne moramo (kao ni prijelaze prema njemu) crtati na dijagramu: podrazumijevamo da riječi za koje se dogodi neka od tih "nemogućih situacija" nisu u domeni funkcije koju Turingov stroj računa. Važno je da ne mora vrijediti obrat: Turingov stroj ne mora nikada ući u stanje $q_x$, a da ipak nikada ne stane. Možemo to usporediti s instrukcijom RAM-stroja $i.\;\goto\;i$ --- ako $\textsc{pc}$ ikad postane $i$, RAM-stroj sigurno ne stane, ali može ne stati i na druge načine.

    Konfiguracije Turingova stroja u konkretnom izračunavanju obično se označavaju skraćeno: ispod trenutno čitanog znaka napišemo trenutno stanje, odnosno umjesto $\bigl(q,n,(t_m)_{m\in\N}\bigr)$ pišemo $t_0t_1\ldots\smash{\underset{q}{t_n}}t_{n+1}\ldots$ --- u takvom zapisu ne pišemo (ali podrazumijevamo) $\bl\ldots$ na kraju.

	Koristeći tu notaciju, početna konfiguracija $\mathcal T_h$ s ulazom $\t{abaa}$ je $\underset{\textsc a}{\t a}\t{baa}$. \\
	Tada je $\mathcal T_h$-izračunavanje s $\t{abaa}$
\begin{multline}
\underset{\textsc a}{\t a}\t{baa}\leadsto
\t c\underset{\textsc b}{\t b}\t{aa}\leadsto
\t{cb}\underset{\textsc b}{\t a}\t a\leadsto
\t{cba}\underset{\textsc b}{\t a}\leadsto
\t{cbaa}\underset{\textsc b }{\bl}\leadsto
\t{cba}\underset{\textsc c}{\t a}\leadsto
\t{cb}\underset{\textsc d}{\t a}\leadsto
\t{c}\underset{\textsc d }{\t b}\t{a}\leadsto
\underset{\textsc d}{\t c }\t{ba}\leadsto\\
\leadsto\t{a}\underset{\textsc a}{\t b}\t{a}\leadsto
\t{ad}\underset{\textsc b}{\t a}\leadsto
\t{ada}\underset{\textsc b}{\bl}\leadsto
\t{ad}\underset{\textsc c}{\t a}\leadsto
\t{a}\underset{\textsc d}{\t d}\leadsto
\t{ab}\underset{\textsc a}{\bl}\leadsto
\t{ab}\bl\underset{\textsc e}{\bl}\lcirclearrowleft\!\text,
\end{multline}
iz čega se vidi izlazni podatak $\t{ab}=\varphi_h(\t{abaa})$. S druge strane, $\mathcal T_h$-izračunavanje s $\t{aba}$
\begin{multline}
\underset{\textsc a}{\t a}\t{ba}\leadsto
\t{c}\underset{\textsc b}{\t b}\t{a}\leadsto
\t{cb}\underset{\textsc b }{\t a}\leadsto
\t{cba}\underset{\textsc b}{\bl}\leadsto
\t{cb}\underset{\textsc c}{\t a}\leadsto
\t{c}\underset{\textsc d}{\t b}\leadsto
\underset{\textsc d}{\t c}\t{b}\leadsto
\t{a}\underset{\textsc a}{\t b}\leadsto
\t{ad}\underset{\textsc b}{\bl}\leadsto
\t{a}\underset{\textsc c}{\t d}\leadsto
\t{}\underset{\textsc f}{\t a}\t d\leadsto
\t{}\underset{\textsc f}{\t a}\t d\leadsto\dotsb%\;\text,
\end{multline}
očito ne stane, što je u skladu s tim da $\t{aba}\notin\dom{\varphi_h}$ (jer je $\dulj{\t{aba}}=3$ neparan broj).
\end{primjer}

%\section{Prateće funkcije jezičnih funkcija}%\label{sec:tikp}
\subsection{Prateće funkcije}

Kao što je već najavljeno, cilj je pokazati ekvivalentnost Turing-modela s RAM-modelom i funkcijskim modelom izračunljivosti. Za početak ćemo koristeći pristup sličan onome iz poglavlja~\ref{ch:univ} dokazati da su Turing-izračunljive jezične funkcije "parcijalno rekurzivne".

Prvo moramo precizirati što to znači. Neka je $\Sigma$ abeceda i $\varphi$ jezična funkcija nad njom. Očito $\varphi$ ne možemo dobiti kompozicijom, primitivnom rekurzijom i minimizacijom iz inicijalnih (brojevnih) funkcija. I da smislimo neke "inicijalne jezične funkcije", kompozicija je jasna (čak jednostavnija nego u brojevnom slučaju, jer su sve funkcije jednomjesne), ali kako definirati primitivnu rekurziju kad sljedbenik riječi nije jedinstven? Kako definirati minimizaciju kad kanonski leksikografski uređaj na $\Sigma^*$ nije dobar uređaj? Kako uopće definirati izračunljive jezike ("relacije") kad karakteristična funkcija jezika nije ni brojevna ni jezična funkcija?

Sve su to problemi o kojima smo već govorili, ponajviše u uvodu; no sada znamo dovoljno o kodiranju da nas to ne treba previše obeshrabriti. Kodirat ćemo $\Sigma^*$ nekom funkcijom $\sigma:=\N\Sigma^*$ (po uzoru na kodiranje $\N^*$ označavamo $\kr w:=\sigma(w)$) te ćemo pomoću tog kodiranja definirati prateću funkciju $\N\varphi=\sigma\circ\varphi\circ\sigma^{\,-1}$, za koju znamo što znači da je parcijalno rekurzivna.
Štoviše, pazit ćemo da $\sigma$ bude \emph{bijekcija} između $\Sigma^*$ i $\N$, tako da će prateće funkcije totalnih funkcija biti opet totalne funkcije. Onda će i \emph{rekurzivne} jezične funkcije biti dobro definirane --- kao totalne izračunljive jezične funkcije, odnosno one čije su prateće funkcije rekurzivne.

%\subsection{Kodiranje znakova i riječi}\label{sec:kSigma}

Prvo kodirajmo abecedu $\Sigma$. Kako je to konačan skup iskoristit ćemo \texttt{enum}-tehniku, kao što smo napravili kod kodiranja tipova instrukcija RAM-stroja~\eqref{eq:enumIns}. Ovdje počinjemo brojiti od $1$ (želimo $0\nin\im{\N\Sigma}$) iz tehničkog razloga koji će uskoro biti jasan.

Mali filozofski problem je u tome što su elementi od $\Sigma$ "apstraktni znakovi" bez ikakve imanentne semantike i međusobnog odnosa, tako da ne možemo fiksirati jedan poredak kao što smo to učinili za tipove RAM-instrukcija. Ipak, za svaku konkretnu abecedu moći ćemo fiksirati kodiranje (\emph{encoding}), a za apstraktne abecede moći ćemo univerzalno kvantificirati tvrdnje u obliku "Za svako kodiranje od $\Sigma$~\ldots", podrazumijevajući ("Zermelov teorem za konačne skupove") da kodiranje \emph{postoji}. U praksi, znakovi će obično biti dio standarda Unikod, pa ih u nedostatku pametnijeg kriterija možemo poredati po rednim brojevima u Unikodu.

\begin{definicija}[{name=[kodiranje abecede]}]
Neka je $\Sigma$ abeceda. Označimo $b:=\card\Sigma$. %(taj broj zovemo \emph{baza} abecede $\Sigma$, iz razloga koji će uskoro postati jasan).

	\emph{Kodiranje} od $\Sigma$ je bilo koja bijekcija $\N\Sigma:\Sigma\leftrightarrow[1\mspace{-1mu}\dd b]$.
\end{definicija}

% \subsection{Pomaknute baze i kodiranje riječi}

Sada bismo mogli kao u definiciji~\ref{def:kodProg} kodirati riječi kao kodove konačnih nizova kodova njihovih znakova --- ali to ne bi bilo bijektivno. Osim toga, kodovi RAM-instrukcija mogli su biti proizvoljno veliki, dok za fiksnu abecedu kodovi znakova mogu biti najviše $b$ --- što sugerira da nam je dovoljno jednostavnije kodiranje.

Najprirodnije kodiranje ograničenih nizova, toliko prirodno da možda nismo ni svjesni kako ga koristimo (za $b=10$) svaki put kad čitamo i pišemo višeznamenkaste brojeve, je \textbf{zapis u bazi} $b$. Problem su početne nule ($\mspace{1mu}(001121)_3=(1121)_3$), što smo riješili početkom kodiranja znakova od $1$, ali smo zato dobili uključenu gornju granicu. Možemo li doista imati zna\-men\-ku~$b$ u bazi $b$? Drugi problem su jednočlane abecede: obični pozicijski brojevni sustavi definiraju se samo za baze $b\ge2$. Postoji i unarni zapis, ali on nije pozicijski --- ili jest?

Zapravo, unarni zapis sasvim odgovara uobičajenom brojevnom zapisu u bazi $b$ za $b=1$: recimo, $(1111)_1=1\cdot1^3+1\cdot1^2+1\cdot1^1+1\cdot1^0=4$, i jedini problem je uključena gornja granica --- u bazi $1$ imamo znamenku $1$. Ali zato nemamo znamenku $0$, i ne smijemo je imati ako želimo jedinstvenost zapisa --- no to upravo rješava prvi problem: ne možemo imati nule na početku ako ih nemamo uopće.

\begin{definicija}[{name=[zapis broja u pomaknutoj bazi]}]
	Neka je $b\in\N_+$, $n\in\N$ te $z_0,z_1,\dotsc,z_{n-1}\in[1\mspace{-1mu}\dd b]$. Zapis u \emph{pomaknutoj bazi} $b$ je %zapis
\begin{equation}\label{eq:pomakbaza}
	(z_{n-1}\dotsm\mspace{2mu} z_0)_b:=\sum\nolimits_{i<n}z_i\cdot b^i\text,
\end{equation}
	dakle isti kao obični zapis u bazi $b$, samo sa znamenkama iz $[1\mspace{-1mu}\dd b]$ umjesto iz $[0\dd b\rangle$.
\end{definicija}

\begin{lema}[{name=[egzistencija i jedinstvenost zapisa u pomaknutoj bazi]}]\label{lm:pomakbaza}
Za svaki $b\in\N_+$, svaki $x\in\N$ ima jedinstveni zapis u pomaknutoj bazi $b$.
\end{lema}
\begin{proof}
Dokaz egzistencije je isti kao i za običnu bazu $b$: uzastopno dijelimo $x$ s $b$ dok ne dobijemo nulu pa ostatke tih dijeljenja zapišemo obrnutim redom. Jedina razlika je što ovdje ostatci moraju biti između $1$ i $b$: ako $x$ nije djeljiv s $b$ ništa se ne mijenja, a ako jest smanjimo količnik za $1$. Recimo, $18$ podijeljeno s $3$ je $5$ i pomaknuti ostatak $3$. Pomaknuti ostatak je primitivno rekurzivna operacija, po primitivno rekurzivnoj verziji teorema o grananju.
\begin{equation}
    \f{mod}'(x,b):=\begin{cases}
        b,&b\mid x\\
        x\bmod b,&\text{inače}
    \end{cases}
\end{equation}

Za dokaz jedinstvenosti treba vidjeti da brojevi različitih duljina zapisa, kao i oni iste duljine zapisa koji se u nekoj znamenci razlikuju, moraju biti različiti. Obje te tvrdnje slijede iz
\begin{multline}
\label{eq:injNSz}
	(tz_{m-1}z_{m-2}\dotsm z_1z_0)_b=
	t\cdot b^m+z_{m-1}\cdot b^{m-1}+z_{m-2}\cdot b^{m-2}+\dotsb
		+z_1\cdot b+z_0\le{}\\{}\le
	t\cdot b^m+b\cdot b^{m-1}+b\cdot b^{m-2}+\dotsb+b\cdot b+b<
	t\cdot b^m+b^m+1\cdot b^{m-1}+\dotsb+1\cdot b^2+1\cdot b+1
		\le{}\\{}\le
	(t+1)b^m+z_{m-1}'\cdot b^{m-1}+\dotsb
		+z_2'\cdot b^2+z_1'\cdot b^1+z_0'\cdot b^0=
        \bigl((t+1)z_{m-1}'\dotsm z_2'z_1'z_0'\bigr)_b
\end{multline}
	--- prva za $t:=0$, a druga za $t:=(\text{prva znamenka slijeva u kojoj se zapisi razlikuju})$. %\\ Sama stroga nejednakost u~\eqref{eq:injNSz} dobije se iz
%\begin{multline}
%\end{multline}

To po tranzitivnosti zapravo znači da smo zapise poredali po duljini, a zapise iste duljine leksikografski (tzv\!.\ \emph{shortlex ordering}).
\end{proof}

\begin{primjer}[{name=[\emph{shortlex ordering} riječi nad dvočlanom abecedom]}]
\emph{Shortlex ordering} $\{\t a,\t b\}^*$ je: $\underset{0}{\varepsilon}$,
$\underset{1}{\t a}$,
$\underset{2}{\t b}$,
$\underset{3}{\t{aa}}$,
$\underset{4}{\t{ab}}$,
$\underset{5}{\t{ba}}$,
$\underset{6}{\t{bb}}$,
$\underset{7}{\t{aaa}}$,
$\underset{8}{\t{aab}}$,
$\underset{9}{\t{aba}}$,~\ldots.
\end{primjer}

\begin{definicija}[{name=[kodiranje riječi]}]
Neka je $\Sigma$ abeceda te $\N\Sigma$ njeno kodiranje.

	Definiramo kodiranje skupa $\Sigma^*$ svih riječi nad $\Sigma$, s
\begin{equation}\label{eq:kodNSz}
	\N\Sigma^*(w):=\kr{\alpha_{n-1}\dotsm\alpha_0}:=\bigl(\N\Sigma(\alpha_{n-1}\mspace{-1mu})\dotsm\mspace{1mu}\N\Sigma(\alpha_0)\bigr)_{b}=\sum\nolimits_{i<n}\N\Sigma(\alpha_i)\cdot b^i\text,
\end{equation}
za svaku riječ $w=\alpha_{n-1}\dotsm\alpha_0\in\Sigma^*$ (uz oznake $n:=\dulj{w}$ i $b:=\card\Sigma$).
\end{definicija}

\begin{primjer}[{name=[prateća funkcija jezične funkcije]}]
U primjeru~\ref{pr:pola} uveli smo abecedu $\Sigma=\{\t a,\t b\}$ i riječ $w_1=\t{aababa}$ nad njom. Za tu abecedu je $b=2$; fiksirajmo kodiranje $\N\Sigma(\t a):=1$, $\N\Sigma(\t b):=2$. Tada je $\kr{w_1}=(112121)_2=73$.
Također je $w_1\in\dom{\varphi_h}$, pa je $73\in\dom{\N\varphi_h}$; a iz $\varphi_h(w_1)=\t{aab}$ vidimo $\N\varphi_h(73)=\kr{\t{aab}}=(112)_2=8$.

Za broj $153$ pretvaranje u pomaknutu bazu $2$ daje
	$\begin{smallmatrix}
153 & 76 & 37 & 18 & 8 & 3 & 1\\
1 & 2 & 1 & 2 & 2 & 1 & 1
\end{smallmatrix}$, dakle $153=(1122121)_2=\kr{\t{aabbaba}}$. Jer je $\dulj{\t{aabbaba}}=7$ neparan broj, $\t{aabbaba}\notin\dom{\varphi_h}$, pa $153\notin\dom{\N\varphi_h}$.
\end{primjer}

Za dekodiranje trebamo, analogno propoziciji~\ref{prop:lhpartprn}, duljinu zapisa te ekstrakciju pojedine znamenke u zadanoj pomaknutoj bazi. %Ipak, prvo to napravimo za obične zapise u bazi, jer je jednostavnije a trebat će nam. Nakon toga ćemo vidjeti što treba promijeniti za zapis u pomaknutoj bazi.

\begin{lema}[{name=[rad sa zapisima u pomaknutoj bazi]}]\label{lm:ldcpprn}
% Možda: umjesto specifikacije napraviti definiciju s točkicom (b=0->b=1)
Postoje primitivno rekurzivne funkcije $\f{slh}^2$, $\f{sdigit}^3$, $\f{sconcat}^3$ i $\f{sprefix}^3$,\newline takve da za sve $b\in\N_+$, za sve $m,n\in\N$ vrijedi:
\begin{labeling}{$\f{sconcat}(m,n,b)$}
    \item[$\f{slh}(n,b)$] je duljina zapisa broja $n$ u pomaknutoj bazi $b$. \item[$\f{sdigit}(n,i,b)$] za $i<\f{slh}(n,b)$, je vrijednost $i$-te znamenke zapisa broja $n$ u pomaknutoj bazi $b$, gdje brojimo od nule slijeva.
    \item[$\f{sconcat}(m,n,b)$] je broj čiji se zapis u pomaknutoj bazi $b$ dobije konkatenacijom istih takvih zapisa za $m$ i $n$ redom. Pišemo ga i kao $m\conc bn$.
    \item[$\f{sprefix}(n,i,b)$] za $i\le\f{slh}(n,b)$, je broj čiji je zapis u pomaknutoj bazi $b$ prefiks (početak) duljine $i$ istog takvog zapisa broja $n$.
\end{labeling}
\end{lema}
%Za fiksni $b$, $\f{sconcat}(m,n,b)$ još pišemo $m\conc b n$, a $\f{Prefix}(m,n,b)$ pišemo $m\preceq_b n$.
\noindent\begin{align}
\label{eq:deflh}
    \f{slh}(n,b)&:=(\mu t\le n)\big(\!
    \textstyle\sum_{i\le t}\!b^i>n
    \big)\\
\label{eq:defconcat}
    \f{sconcat}(m,n,b)&:=m\conc bn:=m\cdot b^{\,\f{slh}(n,b)}+n\\
\label{eq:defprefix}
    \f{sprefix}(n,i,b)&:=(\mu m\le n)(\exists t\le n)\bigl(n=m\conc bt\land\f{slh}(m,b)=i\bigr)\\
\label{eq:defdigit}
    \f{sdigit}(n,i,b)&:=\f{mod}'\bigl(\f{sprefix}\bigl(n,\f{Sc}(i),b\bigr),b\bigr)
\end{align}
\begin{proof}
Za $\f{slh}$, treba uočiti da zapis\=a duljine $i$ ima točno $b^i$. Dakle, samo trebamo zbrajati takve brojeve dok ne prijeđemo $n$. Očito je $\f{slh}(n,b)\le n$.~\eqref{eq:deflh}

Za konkatenaciju, $m$ pomaknemo udesno za duljinu od $n$, i pribrojimo $n$.~\eqref{eq:defconcat}

Pomoću konkatenacije možemo dobiti $\f{sprefix}$: prefiks je ono što se može konkatenirati s nečim tako da se dobije početni zapis $n$. Očito su dijelovi manji ili jednaki $n$.~\eqref{eq:defprefix} %I ovdje: podriječ ima manji kod.

Sada možemo napisati i $\f{sdigit}$: to je zadnja znamenka onog prefiksa čija je duljina za jedan veća od pozicije znamenke.~\eqref{eq:defdigit}
%Sve te funkcije su primitivno rekurzivne, koristeći dosadašnje rezultate.
\end{proof}

\begin{propozicija}[{name=[bijektivnost kodiranja riječi]}]\label{pp:bijkr}
Neka je $\Sigma$ abeceda s kodiranjem $\N\Sigma$.
    Tada je $\N\Sigma^*$ bijekcija između $\Sigma^*$ i $\N$.
\end{propozicija}
\begin{proof}
Označimo $b:=\card\Sigma$. Ako je $w\ne w'$ za $w,w'\in\Sigma^*$, tada su $w$ i $w'$ ili različitih duljina (pa je $\f{slh}(\kr w,b)\ne\f{slh}(\kr{w'},b)$), ili su jednake duljine ali se na nekom mjestu razlikuju (pa je $\f{sdigit}(\kr w,i,b)\ne\f{sdigit}(\kr{w'},i,b)$ za neki $i$).
U svakom slučaju $\kr w\ne\kr{w'}$, pa je $\N\Sigma^*$ injekcija.

	Za surjektivnost, neka je $x\in\N$ proizvoljan. Prema lemi~\ref{lm:pomakbaza}, postoje znamenke $\vec z\in[1\mspace{-1mu}\dd b]^*$ takve da je $x=(\vec z)_b$. Ako sad za svaku $z_i$ označimo $\alpha_i:=\N\Sigma^{-\mspace{-2mu}1}(z_i)\in\Sigma$, riječ $\vec\alpha$ sastavljena od tih znakova ima upravo kod $x$.
\end{proof}

%Sada možemo formalno dokazati da Turing-izračunljivost jezične funkcije povlači parcijalnu rekurzivnost njene prateće funkcije.

\begin{definicija}[{name=[prateća funkcija jezične funkcije]}]\label{def:kodfi}
Neka je $\Sigma$ abeceda, $\N\Sigma$ njeno kodiranje te $\varphi:\Sigma^*\rightharpoonup\Sigma^*$ jezična funkcija nad njom. \emph{Prateća funkcija} od $\varphi$ je brojevna funkcija $\N\varphi$ s domenom $\N\Sigma^*[\dom\varphi]$, zadana s
\begin{equation}\label{eq:kodfidef}
    \N\varphi(\kr{w}):\simeq\kr{\varphi(w)}\text.
\end{equation}
Kako je svaki prirodni broj kod jedinstvene riječi iz $\Sigma^*$, definicija je dobra.
\end{definicija}

\subsection{Kodiranje stanja, trake i funkcije prijelaza}

Kroz čitavu ovu točku imat ćemo fiksiranu abecedu $\Sigma_0$, njeno kodiranje $\N\Sigma_0$ uz oznaku $b':=\card\Sigma_0$, Turing-izračunljivu jezičnu funkciju $\varphi_0$ nad $\Sigma_0$ te fiksni Turingov stroj $\mathcal T_0=(Q_0,\Sigma_0,\Gamma_0,\bl,\delta_0,q_0,q_z)$ koji je računa. Cilj će nam biti, kodirajući komponente i izračunavanje stroja $\mathcal T_0$, dokazati da je $\N\varphi_0$ parcijalno rekurzivna funkcija. To je slično pristupu u poglavlju~\ref{ch:univ}, samo je jednostavnije jer ne moramo pisati interpreter za proizvoljni RAM-program zadan kodom, već samo "ručno" prevesti jedan konkretni Turingov stroj $\mathcal T_0$ u funkcijski jezik.

%\subsection{Kodiranje stanja, radne abecede i trake}

Prvo kodirajmo skup $Q_0$. Kako se radi o konačnom skupu, možemo jednostavno staviti $a:=\card Q_0$ i fiksirati bijekciju $\N Q_0:Q_0\leftrightarrow[0\dd a\rangle$. Za konstruktor trebamo samo fiksirati kod početnog stanja --- prirodnim se čini definirati $\N Q_0(q_0):=0$ --- a što se komponenata tiče, sve što trebamo je usporedba s $q_z$, što ćemo dobiti ako i njegov kod bude fiksni broj --- recimo, $\N Q_0(q_z):=1$.

Hm, hoće li onda $\N Q_0$ biti dobro definirana: što ako je $q_0=q_z$? Definicija Turingova stroja ne sprečava tu mogućnost.
Ipak, $q_0\ne q_z$ smijemo pretpostaviti bez smanjenja općenitosti.

\begin{lema}[{name=[možemo pretpostaviti $q_0\ne q_z$]}]\label{lm:bsomp-q0neqz}
	Za svaki Turingov stroj $\mathcal T$ koji računa neku jezičnu funkciju $\varphi$, postoji \emph{ekvivalentni} (računa istu funkciju $\varphi$) Turingov stroj $\mathcal T'$, kojem se početno i završno stanje razlikuju.
\end{lema}
\begin{proof}
Ako već u $\mathcal T$ vrijedi $q_0\ne q_z$, stavimo $\mathcal T':=\mathcal T$. Inače vrijedi $q_0=q_z$ i tvrdimo da je tada $\varphi$ identiteta na $\Sigma^*$. Doista, za svaku riječ $w\in\Sigma^*$, početna konfiguracija stroja $\mathcal T$ s ulazom $w$, $(q_0,0,w\bl\ldots)=(q_z,0,w\bl\ldots)$, ujedno je i završna konfiguracija, pa izračunavanje uvijek stane ($\varphi$ je totalna) i iz završnog oblika trake čitamo $\varphi(w)=w$.

Dakle, sad samo trebamo konstruirati Turingov stroj s različitim početnim i za\-vrš\-nim stanjem, koji računa identitetu. Jedan takav je
\begin{align}
    \mathcal T'&:=(\{0,1\},\Sigma,\Sigma\cup\{\bl\},\bl,\delta',0,1)\text,\\
%\shortintertext{gdje je}
    \delta'(0,\alpha)&:=(1,\alpha,1)\text{ za sve $\alpha\in\Sigma\cup\{\bl\}$.}
\end{align}
Tada za svaku $w\in\Sigma^*$, $\mathcal T'$\!-izračunavanje s $w$ je $(0,0,w\bl\ldots)\leadsto(1,1,w\bl\ldots)\lcirclearrowleft$, odakle je izlazni podatak opet $w$, odnosno $\mathcal T'$ računa identitetu.
\end{proof}

Slično možemo kodirati i $\Gamma_0$ --- ali kako već imamo kodiranje skupa $\Sigma_0\subset\Gamma_0$, želimo da znakovi ulazne abecede imaju iste kodove. Stoga označimo $b:=\card\Gamma_0$ i proširimo bijekciju $\N\Sigma_0:\Sigma_0\leftrightarrow[1\mspace{-1mu}\dd b']$ do bijekcije $\N\Gamma_0:\Gamma_0\leftrightarrow[0\dd b\rangle$, tako da $\bl$ preslikamo u $0$, a ostale elemente iz $\Gamma_0\!\setminus\Sigma_0$ bijektivno u skup $\langle b'\dd b\rangle$.

Ovaj put smo upotrijebili nulu, kao $\N\Gamma_0(\bl)$. To opravdava frazu "traka je s konačnim nosačem" (praznine su kodirane nulama, pa ne-nul\=a ima konačno mnogo), a bit će esencijalno i za kodiranje trake. Naime, sada imamo sličan problem kao sa stanjem registara RAM-stroja: da bismo kodirali proizvoljnu traku, moramo nekako skupiti kodove beskonačno mnogo ćelija, ali takve da su svi osim konačno mnogo njih jednaki~$0$. Alternativno, želimo "kodiranje" konačnih nizova, ali takvo da dodavanje nule na kraj ne promijeni kod.

U slučaju RAM-registara to smo riješili rastavom na prim-faktore, odnosno malom modifikacijom kodiranja $\N^*$ --- umjesto od $1$, eksponenti su išli od $0$. Možemo li ovdje naći neku malu modifikaciju kodiranja $\Sigma^*$ (zapis u bazi) da dobijemo analogni rezultat?

Možemo, i slična ideja funkcionira: kontraprimjer za injektivnost preslikavanja koje broji znakove od $0$ bit će upravo putokaz kako treba napisati kodiranje trake. Umjesto od $1$, znamenke će ići od $0$. Tamo smo rekli da je $(001121)_3=(1121)_3=43$, no to upravo znači da je broj $43$ prirodno gledati kao kod trake $\t{abaa\bl\bl\bl\ldots}=\t{abaa\bl\ldots}$ --- drugim riječima, ovdje imamo \textbf{obični zapis u (ne pomaknutoj$\mspace{1mu}$) bazi $b$}.

\begin{definicija}[{name=[kodiranje trake Turingova stroja]}]
Za proizvoljnu traku $t:\N\to\Gamma_0$ (koja je skoro svuda $\bl$), definiramo \emph{kod trake} \begin{equation}
	\knk{t}=\knk{t_0t_1t_2\ldots\bl\bl\ldots}:=\sum_{i\in\N}\N\Gamma_0(t_i)\cdot b^i\text{, gdje je $b:=\card\Gamma_0$.}
\end{equation}
%(Usporedite s~\eqref{eq:defkreg}.)
	Zbog konačnosti nosača i činjenice da je $\N\Gamma_0(\mspace{0.5mu}\bl)=0$, samo konačno mnogo članova tog "reda potencija" bit će pozitivno, pa je suma dobro definirana.
\end{definicija}

S ovom idejom postoje dvije smetnje pri konstrukciji početne konfiguracije. Prvo, \textbf{moramo promijeniti bazu} iz $\card\Sigma_0=b'$ u $\card\Gamma_0=b$, jer na traci se mogu naći i znakovi s većim kodovima, kao i praznina (\textbf{uvijek je $b>b'$}, zbog $\Gamma\supset\Sigma$). Drugo, u zapadnom svijetu pišemo riječi slijeva nadesno (i tako doživljavamo traku), ali smo zapis brojeva preuzeli iz arapskog jezika koji se piše u suprotnom smjeru. Zato dodavanje nule \emph{slijeva} u zapis broja u bazi $b$ odgovara dodavanju prazne ćelije \emph{zdesna} pri pomaku udesno od zadnje posjećene ćelije.

Računarci s iskustvom mrežnog programiranja znaju za taj problem. Radi se o \emph{byteorder}-dilemi, sasvim analognoj upravo opisanom problemu, iz sličnih razloga. Većina modernih procesora pamti višebajtne podatke tako da na početnoj adresi podatka stoji najmanje značajni bajt, jer se jedino tako postiže neovisnost o veličini ćelije %se na taj način semantika \emph{casta} pokazivača podudara sa semantikom \emph{casta} pokazanih vrijednosti. Nakon \texttt{int x=0x61626364;}, izraz \texttt{(char)x} ima vrijednost \texttt{0x64}, pa bi se moglo očekivati da i \texttt{*(char*)\&x} ima istu vrijednost. (Gledano s druge strane, 
(nakon \texttt{y=25;} na adresi \texttt{\&y} je bajt $25$, neovisno o tome je li varijabla \texttt y tipa \texttt{char}, \texttt{int} ili \texttt{long~long}), što pojednostavljuje računanje. %kojeg je \texttt y tipa.) %No to je jedino moguće ako se \texttt x stavlja na adrese $[p\dd p+\texttt{sizeof x}\rangle$ tako da se na adresu $p$ stavi bajt \texttt{0x64}, na adresu $p+1$ bajt \texttt{0x63} (za \emph{cast} u \texttt{short}),~\ldots, odnosno "obrnutim" redom (\emph{little-endian}).

No taj redoslijed (\emph{little-endian}) je obrnut u odnosu na to kako smo navikli pisati brojeve u dekadskom zapisu --- i kako smo uostalom napisali taj broj (\t2 pa onda \t5) u naredbi koja inicijalizira \texttt y. To posebno dolazi do izražaja pri mrežnom programiranju: standardi propisuju da se višebajtni brojevi preko mreže prenose redoslijedom \emph{big-endian}, kako bi bilo lakše pratiti što se događa u slučaju greške. Zato mnoge standardne biblioteke imaju funkcije (\texttt{ntoh}/\texttt{hton}) za pretvaranje redoslijeda bajtova iz mrežnog (čitljivijeg) u procesorski (operativniji) i obrnuto. Mi ćemo napraviti slično, usput prenoseći zapis iz jedne baze u drugu.

\begin{lema}[{name=[primitivna rekurzivnost \emph{input\slash output} sustava trake]}]\label{lm:recodeprn}
Postoji primitivno rekurzivna funkcija $\f{Recode}^3$ takva da za svaku riječ $w\in\Sigma_0^*$ vrijede jednakosti
\begin{align}
\SwapAboveDisplaySkip
    \label{eq:recodein}\f{Recode}\bigl(\kr w,b',b\bigr)&=\knk{w\bl\ldots}\text,\\
    \label{eq:recodeout}\f{Recode}\bigl(\knk{w\bl\ldots},b,b'\bigr)&=\kr w\text.
\end{align}
\end{lema}
\begin{proof}
Kao što smo već rekli, $\f{Recode}(n,b_1,b_2)$ samo treba ekstrahirati znamenke od $n$ u bazi $b_1$ te ih slagati obrnutim redom u bazi $b_2$. Kako je $w\in\Sigma_0^*$, u zapisu nema znamenke $0$, pa
možemo koristiti funkcije $\f{slh}$ i $\f{sdigit}$ bez obzira na to je li baza $b_1$ pomaknuta.
\begin{equation}
	\f{Recode}(n,b_1,b_2):=\quad\sum_{\mathclap{i\,<\,\f{slh}(n,b_1\mspace{-1mu})}}\f{sdigit}(n,i,b_1\mspace{-1mu})\cdot{b_2}^i
\end{equation}
Neka je $w=\alpha_0\alpha_1\dotsm\alpha_{l-1}\in\Sigma^*$ proizvoljna ($l:=\dulj{w}$). Tada, ako označimo $n:=\kr w$, vrijedi $\f{slh}(n,b')=l$ i $d_i:=\f{sdigit}(n,i,b')=\N\Sigma_0(\alpha_i)=\N\Gamma_0(\alpha_i)$ za sve $i<l$. Iz toga
\begin{equation}
    \f{Recode}(n,b',b)=\sum_{i<l}d_i\cdot b^i=\sum_{i=0}^{l-1}\N\Gamma_0(\alpha_i)\cdot b^i=\knk{w\bl\ldots}\text,
\end{equation}
i analogno~\eqref{eq:recodeout}. Ključno je bilo da se $\N\Sigma_0$ i $\N\Gamma_0$ podudaraju na svim znakovima $\alpha\in\Sigma_0$.

    Primitivna rekurzivnost slijedi iz lema~\ref{lm:sumprodrek} i~\ref{lm:ldcpprn} te primjera~\ref{pr:addmulpow}.
\end{proof}

\begin{primjer}[{name=[korištenje \emph{input\slash output} sustava trake]}]
Neka je $\Sigma:=\{\t a,\t b,\t c\}\subset\Gamma:=\{\bl,\t a,\t b,\t c,\t A,\t B,\t C\}$, neka je kodiranje zadano redom kojim su znakovi napisani, i neka je $w:=\t{bbc}$. Tada je $\kr w=(223)_3=27$ te $\knk{w\bl\ldots}=(322)_7=163$, dakle $\f{Recode}(27,3,7)=163$ i $\f{Recode}(163,7,3)=27$.
\end{primjer}

%\subsection{Kodiranje funkcije prijelaza}

Na redu je kodiranje funkcije prijelaza $\delta_0$. Mogli bismo se zabrinuti, znajući koliko kodiranje funkcija može biti komplicirano (sjetite se indeksa). Ali $\delta_0$ je \emph{konačna} funkcija (\emph{lookup table}), pa zapravo neće biti problema.

Prvo, $\delta_0$ je funkcija s dva ulaza i tri izlaza, tako da je zapravo kodiramo kroz tri dvomjesne koordinatne funkcije (napomena~\ref{nap:brip}). Drugo, već imamo kodiranja za ulaze i prva dva izlaza, $\N Q_0:Q_0\leftrightarrow[0\dd a\rangle$ i $\N\Gamma_0:\Gamma_0\leftrightarrow[0\dd b\rangle$, samo još trebamo kodirati pomake. Kako oni već jesu "numerički" u $\mathbb Z$, najlakše ih je samo povećati za $1$ da upadnu u $\N$, tako da "pomak ulijevo" $-1$ kodiramo brojem $0$, a "pomak udesno" $1$ kodiramo brojem $2$.

\begin{lema}[{name=[primitivna rekurzivnost funkcije prijelaza]}]\label{lm:newssdprn}
Postoje primitivno rekurzivne funkcije $\f{newstate}$, $\f{newsymbol}$ i $\f{direction}$ koje preslikavaju $\bigl(\N Q_0(q),\N\Gamma_0(\gamma)\bigr)$ redom u $\N Q_0(q')$, $\N\Gamma_0(\gamma')$ i $1+d$, gdje je
$(q',\gamma',d):=\begin{smallcases}
	\delta_0(q,\gamma),& q\ne\mspace{1mu} q_z\\
(q,\gamma,0),&\text{inače}\end{smallcases}\!$.
\end{lema}
\begin{proof}
	Za proizvoljni par $(k,g)\in[0\dd a\rangle\times[0\dd b\rangle$, ako je $k\ne 1$ označimo $(q',\gamma',d):=\delta_0\bigl(\N Q_0^{-\mspace{-2mu}1}(k),\N\Gamma_0^{-\mspace{-2mu}1}(g)\bigr)$ te definirajmo $\f{newstate}(k,g):=\N Q_0(q')$, $\f{newsymbol}(k,g):=\N\Gamma_0(\gamma')$ i $\f{direction}(k,g):=1+d$. Također, za $k=1$, za svaki $g\in[0\dd b\rangle$, dodefinirajmo $\f{newstate}(1,g):=\f{direction}(1,g):=1$ i $\f{newsymbol}(1,g):=g$.

Koliko god to komplicirana pravila bila, njima definirane funkcije su konačne (sve tri imaju domenu $[0\dd a\rangle\times[0\dd b\rangle$ s $ab$ elemenata), pa prema korolaru~\ref{kor:kon0} za svaku od njih postoji primitivno rekurzivna funkcija koja se s njom podudara na $[0\dd a\rangle\times[0\dd b\rangle$ (proširenje nulom). Sada je iz definicije tih triju funkcija jasno da vrijedi tvrdnja leme (sjetimo se, $1=\N Q_0(q_z)$, a $[0\dd a\rangle$ i $[0\dd b\rangle$ su slike od $\N Q_0$ i $\N\Gamma_0$ redom).
\end{proof}

\begin{primjer}[{name=[kodirana tablica prijelaza]}]\label{pr:polatable}
U primjeru~\ref{pr:pola} smo vidjeli funkciju prijelaza $\delta_h$, definiranu s~\eqref{eq:deltapola}. \\ Ako stanja i znakove kodiramo kao
%\begin{equation}
$
    \begin{array}{r|cccccc}
         Q_h& \textsc a& \textsc b& \textsc c& \textsc d& \textsc e& \textsc f \\\hline
         \N Q_h& 0 & 3 & 4 & 5 & 1 & 2
    \end{array}\text{ i }
    \begin{array}{r|cc|ccc}
        \Gamma_h& \t a & \t b & \t c & \t d & \bl \\\hline
        \N\Gamma_h & 1 & 2 & 3 & 4 & 0
    \end{array}
    $,\\
%\end{equation}
tada su funkcije $\f{newstate}$, $\f{newsymbol}$ i $\f{direction}$ redom zadane tablicama
\begin{equation}
\begin{array}{r|ccccccc}
%\f{newstate}
    &0&1&2&3&4&5&\cdots\\\hline
0& 1 & 3 & 3 & 2 & 2 & \multicolumn{1}{|c}{0} & \cdots\\
1& 1 & 1 & 1 & 1 & 1 & \multicolumn{1}{|c}{0} & \cdots\\
2& 2 & 2 & 2 & 2 & 2 & \multicolumn{1}{|c}{0} & \cdots\\
3& 4 & 3 & 3 & 2 & 2 & \multicolumn{1}{|c}{0} & \cdots\\
4& 2 & 5 & 5 & 2 & 2 & \multicolumn{1}{|c}{0} & \cdots\\
5& 2 & 5 & 5 & 0 & 0 & \multicolumn{1}{|c}{0} & \cdots\\ \cline{2-6}
6& 0 & 0 & 0 & 0 & 0 & 0 & \cdots\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots
\end{array}\;\text,\;\;
\begin{array}{r|ccccccc}
%\f{newsymbol}
    &0&1&2&3&4&5&\cdots\\\hline
0& 0 & 3 & 4 & 3 & 4 & \multicolumn{1}{|c}{0} & \cdots\\
1& 0 & 1 & 2 & 3 & 4 & \multicolumn{1}{|c}{0} & \cdots\\
2& 0 & 1 & 2 & 3 & 4 & \multicolumn{1}{|c}{0} & \cdots\\
3& 0 & 1 & 2 & 3 & 4 & \multicolumn{1}{|c}{0} & \cdots\\
4& 0 & 0 & 0 & 3 & 4 & \multicolumn{1}{|c}{0} & \cdots\\
5& 0 & 1 & 2 & 1 & 2 & \multicolumn{1}{|c}{0} & \cdots\\ \cline{2-6}
6& 0 & 0 & 0 & 0 & 0 & 0 & \cdots\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots
\end{array}\;\text{ i }\;\;
%\end{equation}
%\begin{equation}
%\label{eq:directiontable}
\begin{array}{r|ccccccc}
%\f{direction}
    &0&1&2&3&4&5&\cdots\\\hline
0& 2 & 2 & 2 & 0 & 0 & \multicolumn{1}{|c}{0} & \cdots\\
1& 1 & 1 & 1 & 1 & 1 & \multicolumn{1}{|c}{0} & \cdots\\
2& 0 & 0 & 0 & 0 & 0 & \multicolumn{1}{|c}{0} & \cdots\\
3& 0 & 2 & 2 & 0 & 0 & \multicolumn{1}{|c}{0} & \cdots\\
4& 0 & 0 & 0 & 0 & 0 & \multicolumn{1}{|c}{0} & \cdots\\
5& 0 & 0 & 0 & 2 & 2 & \multicolumn{1}{|c}{0} & \cdots\\ \cline{2-6}
6& 0 & 0 & 0 & 0 & 0 & 0 & \cdots\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots
\end{array}\text.\!\!\!\qedhere
\end{equation}
\end{primjer}

\subsection{Kodiranje Turing-izračunavanja}

Upravo dokazana lema~\ref{lm:newssdprn} donekle je analogna lemi~\ref{lm:NextRegCountprn}. Vrijeme je za analogon leme~\ref{lm:RegCountprn}. Za razliku od tih lema, koje su definirale \emph{uniformne} funkcije što su primale RAM-program kao argument, ove će se odnositi na fiksni Turingov stroj $\mathcal T_0$ --- jer je tako lakše, a ne treba nam puna općenitost; sve što će nam kasnije trebati su \emph{neki} indeksi izračunljivih funkcija, a njih smo dobili s RAM-strojevima.

\begin{lema}[{name=[primitivna rekurzivnost $\mathcal T_0$-izračunavanja]}]\label{lm:StateHeadTapeprn}
%Postoje primitivno rekurzivne dvomjesne funkcije $\f{State}$, $\f{Position}$ i $\f{Tape}$, takve da za svaku riječ $w\in\Sigma_0^*$, za svaki $n\in\N$, njihove vrijednosti u $(\kr w,n)$ kodiraju stanje, poziciju i traku konfiguracije Turingova stroja $\mathcal T_0$ nakon $n$ koraka izračunavanja s $w$.
Funkcije definirane sa
\begin{equation}
    \f{State}(\kr w,n):=\N Q_0(q_n)\text,\quad
    \f{Position}(\kr w,n):=p_n\text,\quad
    \f{Tape}(\kr w,n):=\knk{t_n}\text,
\end{equation}
gdje je $\bigl((q_n,p_n,t_n)\bigr)_{n\in\N}$
$\mathcal T_0$-izračunavanje s $w$,
primitivno su rekurzivne.
\end{lema}
\begin{proof}
	Kao i u dokazu leme~\ref{lm:RegCountprn}, upotrijebit ćemo simultanu primitivnu rekurziju. Za inicijalizaciju trebamo funkcije $\f G_1$, $\f G_2$ i $\f G_3$, koje daju vrijednosti traženih funkcija za $n=0$. Stanje počinje od $q_0$ kodiranog nulom, pozicija počinje od nule (lijevi rub), a traka počinje od $w\bl\ldots$, čiji kod se iz $x=\kr w$ može dobiti primjenom funkcije $\f{Recode}$.
\begin{equation}
    \f G_1(x):=\f G_2(x):=0\text,\qquad
    \f G_3(x):=\f{Recode}(x,b',b)\text.
\end{equation}
Dakle, $\f G_1=\f G_2=\f Z$ (inicijalna), a $\f G_3$ je primitivno rekurzivna po lemi~\ref{lm:recodeprn} i propoziciji~\ref{prop:konst}.

	Za korak, trebamo funkcije $\f H_1$, $\f H_2$ i $\f H_3$, od kojih svaka prima po pet argumenata: kod riječi s kojom se računa $x=\kr w$, broj dosad napravljenih koraka izračunavanja $n$, kod prethodnog stanja $q=\N Q_0(q_n)$, prethodnu poziciju $p=p_n$ i kod prethodne trake $t=\knk{t_n}$. Redom trebaju vratiti $\N Q_0(q_{n+1})$, $p_{n+1}$ i $\knk{t_{n+1}\mspace{-2mu}}$. U tome će nam pomoći funkcije iz leme~\ref{lm:newssdprn}, ali na čemu ih pozvati? Prvi argument je kod trenutnog stanja $q$, a drugi je kod trenutno čitanog znaka $g$, koji možemo dobiti kao vrijednost znamenke od $t$ mjesne vrijednosti $b^p$. Ovdje ne možemo koristiti $\f{sdigit}$ jer se na traci mogu nalaziti i praznine, a i jer se mjesne vrijednosti broje zdesna u zapisu --- ali standardni postupak za ekstrakciju znamenke~\eqref{eq:exznamb} funkcionira.

Sada $\f H_1$ samo treba vratiti $\f{newstate}(q,g)$. $\f H_2$ treba vratiti $p$ pomaknut za $\f{direction}(q,g)$, ali za jedan manje jer smo pomake za $d$ kodirali s $d+1$. $\f H_3$ je najkompliciranija: treba $p$-tu znamenku u zapisu $t$ u bazi $b$ zamijeniti znamenkom vrijednosti $\f{newsymbol}(q,g)$. To radimo tako da od $t$ oduzmemo trenutnu mjesnu vrijednost te znamenke $g\cdot b^p$ pa dodamo mjesnu vrijednost nove. Dakle, primitivno rekurzivne funkcije
\begin{align}
    \f H_1(x,n,q,p,t)&:=\f{newstate}(q,g)\text,\\
    \f H_2(x,n,q,p,t)&:=\f{pd}\bigl(p+\f{direction}(q,g)\bigr)\text,\\
    \f H_3(x,n,q,p,t)&:=t\dotminus g\cdot b^p+\f{newsymbol}(q,g)\cdot b^p\text,\\
    \label{eq:exznamb}\text{uz pokratu }g&:=t\div b^p\bmod b\text,
\end{align}
zadovoljavaju specifikaciju s početka odlomka. Sada su $\f{State}$, $\f{Position}$ i $\f{Tape}$ definirane simultanom primitivnom rekurzijom iz $\f G_1$, $\f G_2$, $\f G_3$, $\f H_1$, $\f H_2$ i $\f H_3$, pa su primitivno rekurzivne po propoziciji~\ref{prop:simultrek}. Tvrdnju leme sada dokazujemo matematičkom indukcijom po $n$, sasvim analogno kao u RAM-modelu.

Za $n=0$, početno stanje je $q_0$, pa je $\f{State}(x,0)=\f G_1(x)=\f Z(x)=0=\N Q_0(q_0)$ doista njegov kod. Početna pozicija je $0=\f Z(x)=\f G_2(x)=\f{Position}(x,0)$. Početna traka je $w\bl\ldots$, čiji kod $\knk{w\bl\ldots}$ je prema~\eqref{eq:recodein} jednak $\f{Recode}(\kr w,b',b)=G_3(\kr w)=\f{Tape}(\kr w,0)$.

Sada pretpostavimo da je nakon $k$ koraka, $q:=\f{State}(\kr w,k)$ kod stanja, $p:=\f{Position}(\kr w,k)$ pozicija, a $t:=\f{Tape}(\kr w,k)$ kod trake stroja. Ako je ta konfiguracija završna, tada je $q=\N Q_0(q_z)=1$, pa prema definicijama iz leme~\ref{lm:newssdprn} vrijedi $\f{newstate}(q,g)=\f{direction}(q,g)=1$ i $\f{newsymbol}(q,g)=g$. Tada $\f H_1$ daje $q$, $\f H_2$ daje $\f{pd}(p+1)=\f{pd}\bigl(\f{Sc}(p)\bigr)=p$, a $\f H_3$ daje $t\dotminus g\cdot b^p+g\cdot b^p=t$ (jer je $g=t\div b^p\bmod b\le t\div b^p\le\frac{t}{b^p}$, pa je $g\cdot b^p\le t$, odnosno $\dotminus$ je zapravo $-$). Dakle $\f{State}(\kr w,k+1)=\f{State}(\kr w,k)$, i slično za $\f{Position}$ i $\f{Tape}$, odnosno završna konfiguracija ostaje ista, kao što i treba.

Ako ta konfiguracija nije završna, tad je $q\in[0\dd a\rangle\setminus\{1\}$, pa su vrijednosti $\f{newstate}$, $\f{newsymbol}$ i $\f{direction}$ zadane preko funkcije $\delta_0$ te predstavljaju upravo novo stanje, novi znak na trenutnoj poziciji i pomak na novu poziciju. Recimo, ako s $g$ označimo kod trenutno čitanog znaka, a s $d$ treću komponentu odgovarajuće vrijednosti $\delta_0(q,g)$, tada je $\f{direction}(q,g)=d+1$, pa je
\begin{multline}
    \f{Position}(\kr w,k+1)=\f H_2\bigl(\kr w,k,\f{State}(\kr w,k),\f{Position}(\kr w, k),\f{Tape}(\kr w,k)\bigr)=\\
    =\f H_2(\kr w,k,q,p,t)=
    \f{pd}\bigl(p+\f{direction}(q,g)\bigr)=\f{pd}(p+d+1)=\\
    =\max\,\{p+d+1-1,0\}=\max\,\{\f{Position}(\kr w,k)+d,0\}\text.
\end{multline}
Slično se dobiju i odgovarajuće vrijednosti za $\f{State}(\kr w,k+1)$ i $\f{Tape}(\kr w,k+1)$.
\end{proof}

%\subsection{Prepoznavanje završne konfiguracije i čitanje rezultata}

Pomoću funkcije $\f{State}^2$ možemo prepoznati završnu konfiguraciju --- u njoj će vrijednost te funkcije biti jednaka $\N Q_0(q_z)=1$. Štoviše, ako $\mathcal T_0$-izračunavanje s $w$ stane, tada je broj koraka nakon kojeg se to dogodi upravo najmanji broj za koji vrijedi ta jednakost. (Nemamo probleme kao u primjeru~\ref{pr:Final'}, jer nam je Turingov stroj fiksan i ne prenosimo ga kao kod, a svaki prirodni broj je kod neke riječi iz $\Sigma_0^*$.)

\begin{lema}[{name=[parcijalna rekurzivnost brojenja koraka do zaustavljanja]}]\label{lm:stopprek}
Funkcija $\f{stop}^1$\!, definirana sa
\begin{equation}
    \f{stop}(\kr w):\simeq\text{"broj koraka nakon kojeg $\mathcal T_0$-izračunavanje s $w$ stane",}
\end{equation}
    parcijalno je rekurzivna (s domenom $\dom{\f{stop}}=\dom{\N\varphi_0}=\{\kr w\mid w\in\dom{\varphi_0}\}=:\kr{\dom{\varphi_0}}$).
\end{lema}
\begin{proof}
Tvrdimo da je
\begin{equation}\label{eq:stopdef}
    \f{stop}(x)\simeq\mu n\bigl(\f{State}(x,n)=1\bigr)
\end{equation}
dobivena minimizacijom primitivno rekurzivne relacije.

	Neka je $x\in\N$ proizvoljan i označimo $w:=(\N\Sigma_0^*)^{-\mspace{-2mu}1}(x)$. Ako je $w\in\dom{\varphi_0}$, tada po definiciji~\ref{def:Tcomputefi} $\mathcal T_0$-izračunavanje s $w$ stane --- označimo s $n_0:=\f{stop}(x)$ broj koraka nakon kojeg se to dogodi. Prema lemi~\ref{lm:StateHeadTapeprn} vrijedi $\f{State}(x,n_0)=\N Q_0(q_z)=1$, ali isto tako za sve $n<n_0$ vrijedi $\f{State}(x,n)\ne 1$ --- jer stanje još nije završno, a $\N Q_0$ je injekcija. Dakle $n_0$ je jednak $\mu n\bigl(\f{State}(x,n)=1\bigr)$.

Ako pak $w\notin\dom{\varphi_0}$, tada $\mathcal T_0$-izračunavanje s $w$ ne stane, pa ne postoji $n\in\N$ takav da vrijedi $\f{State}(x,n)=1$ (opet, jer je $\N Q_0$ injekcija) te izraz $\mu n\bigl(\f{State}(x,n)=1\bigr)$ nema vrijednost, baš kao ni $\f{stop}(x)$.
\end{proof}

%Sada napokon možemo dokazati teorem zbog kojeg smo sve ovo radili.

\begin{teorem}[{name=[parcijalna rekurzivnost pratećih Turing-izračunljivih funkcija]}]\label{tm:tikp}
Neka je $\Sigma_0$ abeceda, $\N\Sigma_0$ njeno kodiranje te $\varphi_0$ Turing-izračunljiva funkcija nad njom. Tada je prateća funkcija $\N\varphi_0$ parcijalno rekurzivna.
\end{teorem}
\begin{proof}
Po pretpostavci, postoji Turingov stroj $\mathcal T_0=(Q_0,\Sigma_0,\Gamma_0,\bl,\delta_0,q_0,q_z)$ koji računa $\varphi_0$. Označimo $b':=\card\Sigma_0$ i $b:=\card\Gamma_0$. Primjenjujući na taj $\mathcal T_0$ sve što smo napravili u ovoj točki (kodiramo mu stanja, radnu abecedu u skladu s $\N\Sigma_0$, traku, funkciju prijelaza te izračunavanje s proizvoljnom riječju), dobijemo (među ostalim) funkcije $\f{Recode}$, $\f{Tape}$ i $\f{stop}$, sa svojstvima iz odgovarajućih lema. Tvrdimo da je
\begin{equation}\label{eq:kodfiprek}
    \N\varphi_0(x)\simeq
    \f{Recode}\bigl(\f{Tape}\bigl(x,\f{stop}(x)\bigr),b,b'\bigr)\text,
\end{equation}
	pa je $\N\varphi_0$ parcijalno rekurzivna kao kompozicija takvih. Sama parcijalna jednakost~\eqref{eq:kodfiprek} je zapravo~\eqref{eq:kodfidef} iz definicije~\ref{def:kodfi}, samo izrečena u "izračunljivom obliku". Za svaki $x\in\N$ imamo dva slučaja ovisno o tome je li $w:=(\N\Sigma_0^*)^{-\mspace{-2mu}1}(x)\in\dom{\varphi_0}$.

Ako nije, tada $\N\varphi_0(x)$ nema vrijednost, a niti desna strana od~\eqref{eq:kodfiprek} nema vrijednost --- $\mathcal T_0$ računa $\varphi_0$, pa $w\notin\dom{\varphi_0}$ znači da $\mathcal T_0$-izračunavanje s $w$ ne stane. Tada $x\notin\dom{\f{stop}}$ prema lemi~\ref{lm:stopprek}, a onda po korolaru~\ref{kor:comptot} također $x$ nije ni u domeni desne strane.

Ako je pak $w\in\dom{\varphi_0}$, tada $\mathcal T_0$-izračunavanje s $w$ stane, a prema lemi~\ref{lm:stopprek} to se dogodi nakon $s:=\f{stop}(\kr w)=\f{stop}(x)$ koraka. Prema lemi~\ref{lm:StateHeadTapeprn}, kod trake završne konfiguracije je onda $t:=\f{Tape}(x,s)$, što je $\knk{\varphi_0(w)\bl\ldots}$ jer $\mathcal T_0$ računa $\varphi_0$. Sada je prema~\eqref{eq:recodeout} $\f{Recode}(t,b,b')=\kr{\varphi_0(w)}$, kao što i treba biti.
\end{proof}

\section{Pretvorba RAM-stroja u Turingov stroj}\label{sec:RAM>Turing}

Dokažimo sada obrat teorema~\ref{tm:tikp}. Za parcijalno rekurzivne funkcije imamo kompajler u RAM-strojeve, koji možemo iskoristiti i za kompiliranje u Turingove strojeve. U modernom računarstvu, dolaskom nove arhitekture često ne moramo iznova kompilirati izvorni kod. Ako već imamo kod na sličnoj razini (RAM-program), možemo ga neposredno prevesti ("transpilirati") u kompilirani kod za drugu arhitekturu. To ćemo učiniti ovdje.

Kroz čitavu ovu točku imat ćemo fiksiranu abecedu $\Sigma_0$, njeno kodiranje $\N\Sigma_0$, kodiranje $\sigma=\kr{\cdots}=\N\Sigma_0^*$ zapisom u pomaknutoj bazi $b=\card\Sigma_0$, jezičnu funkciju $\varphi_0$ nad $\Sigma_0$ takvu da je $\N\varphi_0\in\mathscr Comp_1$ te fiksni RAM-algoritam $P_0^1$ koji računa $\N\varphi_0$.

Cilj će nam biti konstruirati Turingov stroj $\mathcal T_0$ koji računa $\varphi_0$, tako da primi ulaz $w$ na traci, kodira ga u $x:=\kr w$, od toga konstruira početnu konfiguraciju RAM-stroja $\mathcal S_0$ s programom $P_0$ i ulazom $x$ ("\hspace{0.1pt}stavi $x$ u $\reg{\mspace{-1mu}1}\mspace{-2mu}$") te simulira redom korake $P_0$-izračunavanja s $x$. Ako\slash kad $\mathcal S_0$ uđe u završnu konfiguraciju $c$, $\mathcal T_0$ će sadržaj $y:=c(\reg0)$ "dekodirati" u riječ $v:=\varphi_0(w)$, obrisati ostatke izračunavanja s trake i premjestiti $v$ na početak. Ako se to nikad ne dogodi, $\mathcal T_0$ će vječno simulirati rad $\mathcal S_0$, odnosno nikad neće otići u završno stanje --- što i treba da bi računao $\varphi_0$, jer činjenica da $P_0$-izračunavanje s $\kr w$ ne stane znači da $w\notin\dom{\varphi_0}$. Efektivno, definiciju prateće funkcije smo "izvrnuli" iznutra van: $\N\varphi_0=\sigma\circ\varphi_0\circ\sigma^{\,-\!1}$ znači $\varphi_0=\sigma^{\,-\!1}\mspace{-2mu}\circ\N\varphi_0\circ\sigma$.

Stroj $\mathcal T_0$ ćemo konstruirati u pet dijelova (\emph{fragmenata}), koji provode razne faze opisanog postupka simulacije stroja $\mathcal S_0$. Da bismo ga opisali, potrebno je precizirati njegova stanja, radnu abecedu $\Gamma$ te prijelaze.

Stanja ćemo uvoditi implicitno i postepeno, specificiranjem funkcije $\delta$. Dodat ćemo još jedno stanje, stanje greške $q_x$, uz standardnu konvenciju da za bilo koji par $(q,\alpha)$ na kojem nismo eksplicitno definirali $\delta$, vrijedi $\delta(q,\alpha):=(q_x,\alpha,-1)$. To je samo birokratski detalj da bi $\delta$ bila totalna, jer $\mathcal T_0$ nikada neće otići u stanje $q_x$: jedini način da računa beskonačno dugo bit će da odgovarajuće $P_0$-izračunavanje ne stane.

U radnoj abecedi se očito moraju nalaziti svi znakovi iz $\Sigma_0$, kodirani po $\N\Sigma_0$ brojevima iz $[1\mspace{-1mu}\dd b]$. Za svaki $t\in[1\mspace{-1mu}\dd b]$ označimo s $\alpha_t:={\N\Sigma_0}^{-\mspace{-2mu}1}(t)$ odgovarajuću "znamenku".  % označit ćemo s $\alpha_t$. Njima predstavljamo "znamenke" od $1$ do $b$ u pomaknutoj bazi $b$.

Za demarkaciju upotrijebljenog dijela trake koristimo graničnik~$\t\$$. Separator~$\t\#$ odvaja dio za ulaz od dijela za računanje (simulaciju). Traka će pri početku rada izgledati otprilike kao $\t\$\bl^*v\t\#u\bl\ldots$, a pri njegovu kraju kao $\t\$v\bl^*u\t\$\bl\ldots$, gdje je $v\in\Sigma_0^*$ dio za ulaz odnosno izlaz, a $u\in(B^m)^*$ dio za reprezentaciju konfiguracije od $\mathcal S_0$. Dakle
%\begin{equation}
    $\Gamma:=\Sigma_0\dcup\{\t\$,\t\#\}\dcup B^m$,
%\end{equation}
gdje je $B^m$ skup koji ćemo kasnije definirati --- taj skup sadržavat će i prazninu $\bl$.

%\subsection{Inicijalizacija RAM-stroja}

Cilj prve faze je pomaknuti riječ za jednu ćeliju desno, stavivši graničnik na početak. %dovesti traku u oblik $\t\$w\bl\ldots$, tako da možemo početi kodirati. Kako je traka na početku $w\bl\ldots$, moramo pomaknuti riječ za jednu ćeliju udesno.

\begin{lema}[{name=[prvi fragment transpiliranog stroja]}]\label{lm:faza1}
	Postoji fragment Turingova stroja koji prevodi početnu konfiguraciju\\ $\underset{n_{\t\$}}{w}=(n_{\t\$},0,w\bl\ldots)$ u konfiguraciju $\t\$w\underset{\mathclap{n_\bl}}{\bl}=(n_\bl,\dulj{w}+1,\t\$w\bl\ldots)$.
\vspace{-6pt}
\end{lema}

\begin{proof}
	Obično se takav pomak radi s desnog kraja, jer inače moramo izvan trake pamtiti znakove koje prenosimo. No sjetimo se uvoda: za Turingov stroj pomaci su teški a pamćenje znakova lagano --- jer je $\Gamma$ konačan, znakove možemo pamtiti u stanjima stroja. Imat ćemo po jedno stanje $n_\alpha$ za prijenos svakog znaka $\alpha\in\Sigma_0\dcup\{\t\$,\bl\}$. %te još dva posebna stanja $n_{\t\$}$ i $n_{\bl}$. %Možemo standardno otići na kraj trake pa pomicati znak po znak udesno%Standardni način da se to napravi je otići na kraj riječi, pa pomicati slova s kraja redom za po jedno mjesto udesno. To možemo i na Turingovu stroju (pokušajte!), ali možemo i jednostavnije: obrisat ćemo prvi znak (zamijeniti ga s $\t\$$) i \emph{zapamtiti ga} u stanju stroja --- 

    Tada, ako u stanju $n_\alpha$ čitamo znak $\beta$, zamjenjujemo ga s $\alpha$ i pamtimo u stanju $n_\beta$~\eqref{d:10}. To objašnjava i zašto je početno stanje $n_{\t\$}$. Nakon što pročitamo i pomaknemo čitavu riječ, nađemo se u stanju $n_{\bl}$ na prvoj praznini nakon nje. %Zamijenimo je s \t\# i pomaknemo se ulijevo~\eqref{d:12}.
\end{proof}

\begin{primjer}[{name=[prvi fragment transpiliranog stroja]}]
Za $\Sigma_0:=\{\t a,\t b\}$, prvi fragment je prikazan dijagramom
\begin{equation}
\begin{tikzpicture}[baseline=(q0)]\label{dia:T1}
\clip (-1,-2.53) rectangle (5.3,2.16);
    \node[state,initial] (q0) {$n_{\t\$}$};
\node[state] (na) [above right=0.25 and 1.5 of q0] (na) {$n_{\t a}$};
\node[state,below right=0.25 and 1.5 of q0] (nb) {$n_{\t b}$};
    \node[state,below right=0.25 and 1.5 of na] (q1) {$n_{\bl}$};
%\node[state,right of=q1] (q2) {$q_0$};
\draw
(q0) edge node[xshift=-5,yshift=8] {\t a:\t\$} (na)
(q0) edge node[xshift=-3,yshift=-9] {\t b:\t\$} (nb)
(na) edge[loop above] node[below left=0.2]{\t a} (na)
(nb) edge[loop below] node[above right=0.2]{\t b} (nb)
(na) edge node[above=0.1]{\bl:\t a} (q1)
(nb) edge[below] node{\bl:\t b} (q1)
(nb) edge[bend left=15] node[left]{\t a:\t b} (na)
(na) edge[bend left=15] node[right]{\t b:\t a} (nb)
(q0) edge[bend right=90,looseness=1.5] node[above left=0.4 and 1.8]{\bl:\t\$} (q1)
	%(q1) edge[dashed] node[above]{\bl:\t\#} (q2)
;
\end{tikzpicture}\text.
\end{equation}
Za ulaz \t{aab} izračunavanje počinje s
   $\underset{\mathclap{n_{\t\$}}}{\t a}\t{ab}\leadsto\t\$\underset{\mathclap{n_{\t a}}}{\t a}\t b\leadsto\t{\$a}\underset{\mathclap{n_{\t a}}}{\t b}\leadsto\t{\$aa}\underset{\mathclap{n_{\t b}}}{\bl}\leadsto\t{\$aab}\underset{\mathclap{n_{\bl}}}{\bl}%\leadsto\t{\$aa}\underset{\mathclap{q_0}}{\t b}\t\#
	$.
\end{primjer}
\vspace{-0.5em}
\begin{equation}
\label{d:10}\tag{$\delta$1}
    \delta(n_\alpha,\beta):=(n_{\beta},\alpha,1)\text{, za sve }\alpha\in\Sigma_0\dcup\{\t\$\}\text{, }\beta\in\Sigma_0\dcup\{\bl\}\\
\end{equation}

Sljedeći korak je konstruirati početnu konfiguraciju od $\mathcal S_0$, desno od separatora \t\# na poziciji $\dulj{w}+1$. Znamo da to mora biti element od $(B^m)^*$, pa pokušajmo s unarnim kodiranjem: cilj nam je na kraj riječi staviti \t\# te $r_1^{\kr w}$ za jedan konkretni element $r_1\in B^m$. %Što je točno $r_1$ (i čitav $B^m$), reći ćemo u idućoj točki.%, ali zasad ga samo tretiramo kao zasebni znak (baš kao \bl).

\begin{lema}[{name=[drugi fragment transpiliranog stroja]}]\label{lm:faza2}
Postoji fragment Turingova stroja koji prevodi konfiguraciju\newline $\T{$\t\$w$}{n_\bl}{\bl}{}=(n_\bl,\dulj w+1,\t\$w\bl\ldots)$ u konfiguraciju $\t\$\bl^{\dulj w}\t\#\underset{\mathclap{p_0}}{r_1}^{\!\kr w}=(p_0,\dulj w+2,\t\$\bl^{\dulj w}\t\#r_1{}^{\!\kr w}\bl\ldots)$.
\end{lema}
\vspace{-1em}
\noindent\begin{gather*}
\label{d:20}\tag{$\delta$2a}\delta(n_{\bl},\bl):=(q_0,\t\#,-1)\\
\label{d:21}\tag{$\delta$2b}\delta(q_0,\alpha_t):=(q_1,\alpha_{t-1},1)\text{, za sve }t\in[2\dd b]\\
\label{d:22}\tag{$\delta$2c}\delta(q_1,\alpha):=(q_1,\alpha,1)\text{, za sve }\alpha\in\Sigma_0\mathbin{\dcup}\{\t\#,r_1\}\\
\label{d:23}\tag{$\delta$2d}\delta(q_1,\bl):=(q_0,r_1,-1)\\
\label{d:24}\tag{$\delta$2e}\delta(q_0,\gamma):=(q_0,\gamma,-1)\text{, za }\gamma\in\{\t\#,r_1\}\\
\label{d:25}\tag{$\delta$2f}\delta(q_0,\alpha_1):=(q_0,\alpha_b,-1)\\
\label{d:26}\tag{$\delta$2g}\delta(q_0,\gamma):=(q_2,\gamma,1)\text{, za }\gamma\in\{\t\$,\bl\}\\
\label{d:27}\tag{$\delta$2h}\delta(q_2,\alpha_b):=(q_1,\bl,1)\\
\label{d:28}\tag{$\delta$2i}\delta(q_2,\t\#):=(p_0,\t\#,1)
\end{gather*}
\begin{proof}
%To je pretvorba zapisa između različitih pomaknutih baza:
	Prvo postavimo separator na trenutnu poziciju~\eqref{d:20}. Zatim broj $x:=\kr w$ čitamo u pomaknutoj bazi~$b$ pomoću znamenaka $\alpha_t,t\in[1\mspace{-1mu}\dd b]$ te pišemo unarno (u pomaknutoj bazi~$1$) pomoću znamenke~$r_1$. To se može riješiti tako da "dekrementiramo" $w$, za svaki uspješni dekrement dodajući po jedan $r_1$ na kraj.

Zapis u pomaknutoj bazi dekrementiramo slično kao i zapis u običnoj bazi. Ako zadnji znak nije $\alpha_1$, smanjimo njegov kod za $1$~\eqref{d:21} i odemo desno~\eqref{d:22} do prvog razmaka, koji zamijenimo s $r_1$~\eqref{d:23} i vraćamo se ponovo lijevo~\eqref{d:24}. Ako naiđemo na $\alpha_1$, zamijenimo ga "najvećom znamenkom" $\alpha_b$ i nastavljamo smanjivati dalje lijevo~\eqref{d:25}. Ako smanjujući dođemo do lijevog ruba broja~\eqref{d:26}, prvu znamenku mu obrišemo~\eqref{d:27}. %Ako smo ostali bez znamenaka, gotovi smo: 
Na kraju odemo desno iza separatora, u stanje $p_0$~\eqref{d:28}.

Za dokaz da to stvarno dovede do željene konfiguracije dovoljno je primijetiti da se nakon svakog prolaza lijevo-desno  nađemo ponovo u stanju $q_0$, s pozicijom pri desnom kraju trake oblika $\t\$\bl^{\dulj w-\dulj{w'}}w'\t\#r_1^{\kr w-\kr{w'}}$. Na početku je to istina jer je $w=w'$ i još nemamo nijedan $r_1$, u svakom koraku ostaje istina jer se dekrementom $\kr{w'}$ smanjuje za $1$ dok se broj znakova $r_1$ povećava za $1$, a na kraju onda moramo imati $\t\$\bl^{\dulj w}\t\#r_1^{\kr w}$, jer je tada $w'=\varepsilon$ s kodom $\kr{\varepsilon}=0$.
\end{proof}

\begin{primjer}[{name=[drugi fragment transpiliranog stroja]}]
Za $\Sigma_0:=\{\t a,\t b,\t c,\t d\}$, drugi fragment je prikazan dijagramom
\begin{equation}
\begin{tikzpicture}[baseline=(q4)]\label{dia:T2}
%\clip (-1,-2.53) rectangle (8.5,2.16);
\node[state] (q2) {$q_0$};
\node[state,below of=q2] (q3) {$q_1$};
\node[state,below right=0.75 and 2 of q2] (q4) {$q_2$};
\node[state,right of=q4] (p0) {$p_0$};
\node[state,left of=q2] (nb) {$n_\bl$};
\draw
(q2) edge node[left,align=left] {\t d:\t c\\\t c:\t b\\\t b:\t a} (q3)
(q2) edge[dashed, loop right] node[right]{$\t\#,r_1,\t a$:\t d} (q2)
(q2) edge node[below,xshift=-5,yshift=4]{$\t\$,\bl$} (q4)
(q3) edge[loop left] node[left]{$\t\#,r_1,\Sigma_0$} (q3)
(q3) edge[dashed,bend left=60] node[left]{\bl:$r_1$} (q2)
(q4) edge node[below,xshift=3]{\t d:\bl} (q3)
(q4) edge node[above]{\t\#} (p0)
(nb) edge[dashed] node[above] {\bl:\t\#} (q2)
;
\end{tikzpicture}\;\text.
\end{equation}
Za riječ $\t{aab}$ imamo šetnju kroz konfiguracije (pišemo samo neke od njih):
\begin{multline*}
\T{\$aab}{n_\bl}{\bl}{}\leadsto
\T{\$aa}{q_0}{b}{\#}\leadsto
\T{\$aaa}{q_1}{\#}{}\leadsto
\T{\$aaa\#}{q_1}{\bl}{}\leadsto
\T{\$aaa}{q_0}{\#}{\t{$r_1$}}\leadsto^4
%\T{\$aa}{q_0}{a}{\#\t{$r_1$}}\leadsto
%\T{\$a}{q_0}{a}{d\#\t{$r_1$}}\leadsto
%\T{\$}{q_0}{a}{dd\#\t{$r_1$}}\leadsto{}\\
%{}\leadsto
\T{}{q_0}{\$}{ddd\#\t{$r_1$}}\leadsto
\T{\$}{q_2}{d}{dd\#\t{$r_1$}}\leadsto
\T{\$\bl}{q_1}{d}{d\#\t{$r_1$}}\leadsto^4{}\\{}\leadsto^4
\T{\$\bl dd\#\t{$r_1$}}{q_1}{\bl}{}\leadsto
\T{\$\bl dd\#}{q_0}{\t{$r_1$}}{\t{$r_1$}}\leadsto^2
%\T{\$\bl dd}{q_0}{\#}{\t{$r_1r_1$}}\leadsto
%{}\leadsto
\T{\$\bl d}{q_0}{d}{\#\t{$r_1^2$}}\leadsto
\T{\$\bl dc}{q_1}{\#}{\t{$r_1^2$}}\leadsto^3
\T{\$\bl dc\#\t{$r_1^2$}}{q_1}{\bl}{}
\leadsto^4\T{\$\bl d}{q_0}{c}{\#\t{$r_1^3$}}\leadsto^*
\T{\$\bl d}{q_0}{b}{\#\t{$r_1^4$}}\leadsto^*{}\\
	{}\leadsto^*\T{\$\bl d}{q_0}{a}{\#\t{$r_1^5$}}\leadsto^*%{}\\
%{}\leadsto^*
\T{\$\bl c}{q_0}{d}{\#\t{$r_1^6$}}\leadsto^*
\T{\$\bl c}{q_0}{a}{\#\t{$r_1^9$}}\leadsto^*
    \T{\$\bl b}{q_0}{a}{\#\t{$r_1^{13}$}}
    \leadsto^*
\T{\$\bl a}{q_0}{a}{\#\t{$r_1^{17}$}}\leadsto^*
\T{\$\bl\bl}{q_0}{d}{\#\t{$r_1^{18}$}}\leadsto^*
\T{\$\bl\bl}{q_0}{a}{\#\t{$r_1^{21}$}}\leadsto{}\\
{}\leadsto
\T{\$\bl}{q_0}{\bl}{d\#\t{$r_1^{21}$}}\leadsto
\T{\$\bl\bl}{q_2}{d}{\#\t{$r_1^{21}$}}\leadsto
    \T{\$\bl\bl\bl}{q_1}{\#}{\t{$r_1^{21}$}}
    \leadsto^*
\T{\$\bl\bl\bl\#\t{$r_1^{21}$}}{q_1}{\bl}{}\leadsto^*
\T{\$\bl\bl}{q_0}{\bl}{\#\t{$r_1^{22}$}}\leadsto
\T{\$\bl\bl\bl}{q_2}{\#}{\t{$r_1^{22}$}}\leadsto%{}\\
%{}\leadsto
\T{\$\bl\bl\bl\#}{p_0}{\t{$r_1^{22}$}}{}\text,
\end{multline*}
što je točno kako treba biti jer je $b=4$, pa je $\kr{\t{aab}}=(112)_4=22$. "Invarijanta petlje" zadovoljena je u svim istaknutim konfiguracijama gdje se $q_0$ nalazi ispod zadnjeg znaka prije separatora: npr.\ za $\t{\$\bl cd\#$r_1^6$}$ je $w'=\t{cd}$, čiji je kod $\kr{\mspace{-1mu}\t{cd}}=(34)_4=16$, a $\kr w-\kr{w'}=22-16=6$.
\end{primjer}

%I to je to. Spremni smo za simulaciju $P_0$-izračunavanja s $\kr w$.

\subsection{Registri kao tragovi trake}

Vrijeme je da opišemo kako ćemo točno reprezentirati konfiguraciju RAM-stroja $\mathcal S_0$ na traci.  Zapravo, vrijednost programskog brojača je jedna od konačno mnogo njih i na njoj su dopuštene proizvoljne transformacije, pa ju je bolje prikazati kroz stanje stroja. Na traci će stajati samo stanje registara --- i to samo onih relevantnih. U tu svrhu, označimo s $m:=m_{P_0^1}=\max\,\{m_{P_0},2\}$ širinu algoritma $P_0^1$; tada znamo da je dovoljno pratiti prvih $m$ registara.

Kako to najbolje učiniti? Kao što smo rekli na početku ovog poglavlja, jezični model je "transponirani" brojevni model: u jezičnom modelu broj ćelija nije ograničen, ali broj mogućih sadržaja svake ćelije jest, dok je u brojevnom modelu obrnuto. To znači da možemo stanje relevantnih (prvih $m$) registara prikazati kao riječ nad "abecedom $m$-bitnih procesorskih riječi"
\begin{equation}
\renewcommand{\arraystretch}{0.1}
    B^m:=\prod_{i<m}\{\t\textopenbullet,\t\textbullet\}=\bigl\{\left[\begin{array}{@{}l@{}}\beta_0\\[0mm]
    %\MTFlushSpaceAbove
        \vdotswithin{\beta}\\[1mm]
    \beta_{m-1}\end{array}\right]\bigm|(\forall i<m)(\beta_i\in\{\t\textopenbullet,\t\textbullet\})\bigr\}\text,
\end{equation}
tako da se dio trake desno od separatora sastoji od $m$ "redaka" (\emph{tragova}), u svakom od kojih piše $\t\textbullet^t\t\textopenbullet\dotsm$, gdje je $t$ sadržaj odgovarajućeg registra. U tom kontekstu, $B^m$ je "prostor stupaca" sa svim ($2^m$ njih) stupcima znakova $\t\textbullet$ i $\t\textopenbullet$ visine $m$. Recimo,
\begin{equation}\label{eq:B4}
\renewcommand{\arraystretch}{0.1}
    B^4:=\biggl\{
    \begin{array}{c}
    \t\textopenbullet\\
    \t\textopenbullet\\
    \t\textopenbullet\\
    \t\textopenbullet
    \end{array},
    \begin{array}{c}
    \t\textbullet\\
    \t\textopenbullet\\
    \t\textopenbullet\\
    \t\textopenbullet
    \end{array},
    \begin{array}{c}
    \t\textopenbullet\\
    \t\textbullet\\
    \t\textopenbullet\\
    \t\textopenbullet
    \end{array},
    \begin{array}{c}
    \t\textbullet\\
    \t\textbullet\\
    \t\textopenbullet\\
    \t\textopenbullet
    \end{array},
    \begin{array}{c}
    \t\textopenbullet\\
    \t\textopenbullet\\
    \t\textbullet\\
    \t\textopenbullet
    \end{array},
    \begin{array}{c}
    \t\textbullet\\
    \t\textopenbullet\\
    \t\textbullet\\
    \t\textopenbullet
    \end{array},
    \begin{array}{c}
    \t\textopenbullet\\
    \t\textbullet\\
    \t\textbullet\\
    \t\textopenbullet
    \end{array},
    \begin{array}{c}
    \t\textbullet\\
    \t\textbullet\\
    \t\textbullet\\
    \t\textopenbullet
    \end{array},
    \begin{array}{c}
    \t\textopenbullet\\
    \t\textopenbullet\\
    \t\textopenbullet\\
    \t\textbullet
    \end{array},
    \begin{array}{c}
    \t\textbullet\\
    \t\textopenbullet\\
    \t\textopenbullet\\
    \t\textbullet
    \end{array},
    \begin{array}{c}
    \t\textopenbullet\\
    \t\textbullet\\
    \t\textopenbullet\\
    \t\textbullet
    \end{array},
    \begin{array}{c}
    \t\textbullet\\
    \t\textbullet\\
    \t\textopenbullet\\
    \t\textbullet
    \end{array},
    \begin{array}{c}
    \t\textopenbullet\\
    \t\textopenbullet\\
    \t\textbullet\\
    \t\textbullet
    \end{array},
    \begin{array}{c}
    \t\textbullet\\
    \t\textopenbullet\\
    \t\textbullet\\
    \t\textbullet
    \end{array},
    \begin{array}{c}
    \t\textopenbullet\\
    \t\textbullet\\
    \t\textbullet\\
    \t\textbullet
    \end{array},
    \begin{array}{c}
    \t\textbullet\\
    \t\textbullet\\
    \t\textbullet\\
    \t\textbullet
    \end{array}
    \biggr\}\text.
\end{equation}
Konkretno, ako (za $m=4$) u nekom trenutku imamo konfiguraciju $(1,4,0,5,0,0,\dotsc\mspace{-1mu})$, uz $\dulj w=7$, na traci će biti
\begin{equation}\label{eq:bitmap}
\renewcommand{\arraystretch}{0.1}
    \t{\$\bl\bl\bl\bl\bl\bl\bl\#}\begin{array}{@{}c@{}}
    \t\textbullet\\
    \t\textbullet\\
    \t\textopenbullet\\
    \t\textbullet
    \end{array}
    \begin{array}{@{}c@{}}
    \t\textopenbullet\\
    \t\textbullet\\
    \t\textopenbullet\\
    \t\textbullet
    \end{array}
    \begin{array}{@{}c@{}}
    \t\textopenbullet\\
    \t\textbullet\\
    \t\textopenbullet\\
    \t\textbullet
    \end{array}
    \begin{array}{@{}c@{}}
    \t\textopenbullet\\
    \t\textbullet\\
    \t\textopenbullet\\
    \t\textbullet
    \end{array}
    \begin{array}{@{}c@{}}
    \t\textopenbullet\\
    \t\textopenbullet\\
    \t\textopenbullet\\
    \t\textbullet
    \end{array}
    \begin{array}{@{}c@{}}
    \t\textopenbullet\\
    \t\textopenbullet\\
    \t\textopenbullet\\
    \t\textopenbullet
    \end{array}
    \begin{array}{@{}c@{}}
    \t\textopenbullet\\
    \t\textopenbullet\\
    \t\textopenbullet\\
    \t\textopenbullet
    \end{array}
    \begin{array}{@{}c@{}}
    \t\textopenbullet\\
    \t\textopenbullet\\
    \t\textopenbullet\\
    \t\textopenbullet
    \end{array}
    \begin{array}{@{}c@{}}
    \t\textopenbullet\\
    \t\textopenbullet\\
    \t\textopenbullet\\
    \t\textopenbullet
    \end{array}
    \begin{array}{@{}c@{}}
    \t\textopenbullet\\
    \t\textopenbullet\\
    \t\textopenbullet\\
    \t\textopenbullet
    \end{array}\dotsm\text,
\end{equation}
iz čega vidimo dvije stvari. Prvo, $\bl$ mora biti prvi element naveden u $B^m$, koji ima sve kružiće prazne. Tako postižemo da traka bude prazna od nekog mjesta nadalje (konkretno, maksimum svih $m$ vrijednosti u registrima), odnosno da bude s konačnim nosačem. Drugo, naš znak $r_1$, koji smo upotrijebili da postavimo $\reg1$ na ulaznu vrijednost $\kr w$, je treći element u $B^m$, napisan transponirano kao $(\t{\textopenbullet\textbullet\textopenbullet}^{m-2})^\intercal$. Stupčano,
\begin{equation}
\renewcommand{\arraystretch}{0.1}
    \bl\,:=\begin{array}{c}
    \t\textopenbullet\\
    \t\textopenbullet\\
        \t\textopenbullet\\[0mm]
    %\MTFlushSpaceAbove
        \vdotswithin{\t\textopenbullet}\\[1mm]
    \t\textopenbullet
    \end{array}\text{,\qquad}
    r_1:=\begin{array}{c}
    \t\textopenbullet\\
    \t\textbullet\\
        \t\textopenbullet\\[0mm]
    %\MTFlushSpaceAbove
        \vdotswithin{\t\textopenbullet}\\[1mm]
    \t\textopenbullet
    \end{array}\text.
\end{equation}

\begin{primjer}[{name=[dodavanje znaka na kraj riječi]}]\label{pr:+a}
	Nad abecedom $\Sigma:=\{\t a,\t b\}$ kodiranom s $\{\t a\mapsto1,\t b\mapsto2\}$ pogledajmo jezičnu funkciju "dopisivanje \t a zdesna", $\varphi_{\t a}(w):=w\t a$. Baza je $b=2$, pa je prateća funkcija $\N\varphi_{\t a}(\kr w)=\kr{w\t a}=\kr w\conc2\kr{\t a}=\kr w\cdot2^{\,\f{slh}(\kr{\t a},2)}+\kr{\t a}=2^{\dulj{\t a}}\cdot\kr w+1$, odnosno $\N\varphi_{\t a}(x)=2x+1$. Očito je $\N\varphi_{\t a}\in\mathscr Comp_1$: računa je jednostavni RAM-program
\begin{align}
\SwapAboveDisplaySkip\label{eq:+aprog}
    P_{\t a}:=\begin{prog}
    0.&\incr0\\
    1.&\decr14\\
    2.&\incr0\\
    3.&\goto\;0
    \end{prog}
\end{align}
	širine $m=2$. Za ulaznu riječ $\t{ab}$ je $\kr{\t{ab}}=(\mspace{-0.5mu}12)_2=4$, pa je konfiguracija Turingova stroja kroz faze (početna, nakon prve faze i nakon druge faze)
\begin{equation}\label{eq:+afaze}
\renewcommand{\arraystretch}{0.1}
    \T{}{n_{\t\$}}{a}{b}\leadsto^*
\T{\$ab}{n_\bl}{\bl}{}\leadsto^*
    \T{\$\boo\boo\#}{\mund{p_0}}{\boi}{\boi\boi\boi}\,\text{.\qedhere}
\end{equation}
%te smo spremni za početak simulacije.
\end{primjer}

Rekli smo da ćemo vrijednost programskog brojača držati u stanju stroja --- i to je već učinjeno kroz supskript stanja $p_0$: ta nula znači da je \textsc{pc} upravo postao $0$. Općenito, za $P_0$ duljine $n:=n_{P_0}$ imat ćemo stanja $p_i,i\in[0\dd n]$, pri čemu će ulazak u stanje $p_n$ značiti završetak $P_0$-izračunavanja.

\begin{definicija}[{name=[$m$-reprezentacija RAM-konfiguracije]}]
	Neka je $P^1$ RAM-algoritam širine $m$ te $c=(r_0,r_1,\dots,r_{m-1},0,0,\dots,pc)$ konfiguracija RAM-stroja s programom $P$. Tada je \emph{$m$-reprezentacija} od $c$ konfiguracija Turingova stroja sa stanjem $p_{pc}$, trakom oblika $\t\$\bl^k\t\#v\bl\dots$ i pozicijom većom od $k$ --- pri čemu je $v$ riječ nad $B^m$ u čijem $i$-tom tragu piše $\t\textbullet^{r_i}\t\textopenbullet^{\dulj v-r_i}$, za sve $i\in[0\dd m\rangle$.
%Za $k,m,n\in\N$ takve da je $m\ge 2$, za proizvoljnu RAM-konfiguraciju $c$ sa svojstvima $c(\reg j)=0$ za sve $j\ge m$ i $c(\textsc{pc})\le n$, \emph{reprezentacija} je Turing-konfiguracija
%\begin{equation}
%Turing_{kmn}(c):=\biggl(p_{c(\textsc{pc})},k+2,\t\$\bl^k\t\#\!\left[\begin{array}{@{}l@{}}
%\renewcommand{\arraystretch}{0.1}
%\t\textbullet^{c(\reg0)}\t\textopenbullet\dotsm\\
%\t\textbullet^{c(\reg1)}\t\textopenbullet\dotsm
%\MTFlushSpaceBelow
%\vdotswithin{\text\textbullet}
%\MTFlushSpaceBelow
%\t\textbullet^{c(\reg{m-1})}\t\textopenbullet\dotsm
%\end{array}\right.\biggr)\text{.\;\qedhere}
%\end{equation}
\end{definicija}

Recimo,~\eqref{eq:bitmap} je primjer trake $4$-reprezentacije konfiguracije $(1,4,0,5,0,0,\dots\mspace{-1mu})$. Također, zadnja konfiguracija u~\eqref{eq:+afaze} je $2$-reprezentacija početne konfiguracije RAM-stroja s programom $P_{\t a}$ iz~\eqref{eq:+aprog}, s ulazom \t{ab}.

Ipak, stanja $p_i$ nisu dovoljna za izvršavanje RAM-instrukcija: za svaki $i<n$ imamo još jedno stanje $s_i$, koje tome služi. Stanje $p_i$ je "pripremno stanje" za $s_i$, s jedinim zadatkom fiksiranja pozicije odmah nakon znaka $\t\#$.

%\begin{lema}[{name=[{treći fragment transpiliranog stroja, priprema za instrukciju}]}]\label{lm:pi>si}
%Za svaki $i\in[0\dd n\rangle$, postoji fragment Turingova stroja koji prevodi bilo koju konfiguraciju oblika $(p_i,t,\t\$\bl^k\,\t\#v\bl\ldots)$, gdje su $v\in(B^m)^*$ i $t>k\in\N$, u konfiguraciju $(s_i,k+2,\t\$\bl^k\,\t\#v\bl\ldots)$.
%\end{lema}
%\begin{proof}
%Dijagramatski,
%\begin{tikzpicture}[baseline=0]
%\node[state] (pi) {$p_i$};
%\node[state, right of=pi] (si) {$s_i$};
%\draw
%(pi) edge[loop left,dashed] node[left]{$B^m$} (pi)
%(pi) edge[below] node{$\t\#$} (si)
%;
%\end{tikzpicture}\;.
%\end{proof}

%\subsection{Izvršavanje pojedinih RAM-instrukcija}

Da bismo implementirali prijelaze iz stanja $s_i$, moramo naučiti "adresirati bitove" na traci $m$-reprezentacije. Svaki element od $B^m$ vidimo kao $m$-bitnu riječ, koristeći za promjenu pojedinog bita istu tehniku kao "pravi" procesor: čitavu procesorsku riječ zamijenimo drugom, koja se podudara s njom u svim bitovima osim onog koji želimo promijeniti. Primjerice, ako na traci~\eqref{eq:bitmap} želimo "dekrementirati $\reg1$", zamijenit ćemo njen trinaesti znak $(\t{\textopenbullet\textbullet\textopenbullet\textbullet})^\intercal$ znakom $(\t{\textopenbullet\textopenbullet\textopenbullet\textbullet})^\intercal$, devetim na popisu~\eqref{eq:B4}.

\begin{definicija}[{name=[funkcija prijelaza u određenom tragu]}]\label{def:trag}
Neka je $j\in[0\dd m\rangle$, neka su $q,q'\in Q$, neka su $\beta,\beta'\in B:=\{\t\textopenbullet,\t\textbullet\}$ te neka je $d\in\{-1,1\}$. Pišemo $\delta_{(j)}(q,\beta):=(q',\beta',d)$ kao pokratu za:
$\delta(q,\gamma):=(q',\gamma',d)$\text,
za sve $\gamma,\gamma'\in B^m$ takve da je $\gamma_j=\beta$, $\gamma'_j=\beta'$ te $\gamma_i=\gamma'_i$ za sve $i\in[0\dd m\rangle\setminus\{j\}$.

U dijagramima, na strelici od $q$ prema $q'$ pišemo $\beta\t:\beta'\texttt@j$, ili $\beta\texttt@j$ ako je $\beta'=\beta$.
\end{definicija}


\subsection{Simulacija RAM-izračunavanja}

\begin{lema}[{name=[{izvršavanje RAM-instrukcija na Turingovu stroju}]}]\label{lm:gadgets}
    Neka je $P_0=:\begin{prog}i.&I_t\end{prog}_{t<n}$ (širine $m$). Tada za svaki $i<n$ postoji fragment Turingova stroja, koji prevodi svaku $m$-reprezentaciju svake $\mathcal S_0$-konfiguracije $c$ kojoj je $c(\textsc{pc})=i$, u neku $m$-reprezentaciju $\mathcal S_0$-konfiguracije $d$, gdje $c\leadsto d$ po programu $P_0$.
\end{lema}
\begin{proof}
Traženi fragment počinje s radom u stanju $p_i$ na poziciji većoj ili jednakoj poziciji separatora $k$, a treba završiti u stanju $p_{i'}$ za $i':=d(\textsc{pc})$ na poziciji s istim svojstvom. Za početak, dok god čitamo znak iz $B^m$, pomičemo se lijevo~\eqref{d:31}. Kad pročitamo \t\#, pomaknemo se desno~\eqref{d:32}. 
\begin{gather*}
	\SwapAboveDisplaySkip
\label{d:31}\tag{$\delta$3a}
    \delta(p_i,\gamma):=(p_i,\gamma,-1)\text{, za sve }\gamma\in B^m\\
\label{d:32}\tag{$\delta$3b}
    \delta(p_i,\t\#):=(s_i,\t\#,1)
\end{gather*}

Tako dođemo u stanje $s_i$, na poziciju $k+1$. Zbog $c(\textsc{pc})=i<n=n_P$ konfiguracija $c$ sigurno nije završna, pa postoji instrukcija $I_i$. Dalji postupak ovisi o njenom tipu.

Ako je $I_i$ tipa $\inc$, recimo $i.\;\incr j$, trebamo otići do kraja znakova \t\textbullet\ u tragu $j$~\eqref{d:41} i dopisati još jedan \t\textbullet\ tamo, a zatim se pripremiti za sljedeću instrukciju, onu rednog broja $i+1$~\eqref{d:42}.
\begin{gather*}
\SwapAboveDisplaySkip
\label{d:41}\tag{$\delta$3c}
    \delta_{(j)}(s_i,\t\textbullet):=(s_i,\t\textbullet,1)\\
\label{d:42}\tag{$\delta$3d}
    \delta_{(j)}(s_i,\t\textopenbullet):=(p_{i+1},\t\textbullet,-1)
\end{gather*}
Ako je $I_i$ tipa $\dec$, recimo $i.\;\decr jl$, trebamo kao i za $\inc$ doći do kraja znakova~\t\textbullet~\eqref{d:51}, a kada pročitamo \t\textopenbullet, pomaknuti se lijevo u novo "stanje odluke" $t_i$~\eqref{d:52}. Ako u tom stanju čitamo $\t\#$, znači da je $c(\reg j)=0$, pa prelazimo na instrukciju rednog broja $l$~\eqref{d:53}. Ako ne, tada u tragu $j$ zamijenimo \t\textbullet\ s \t\textopenbullet\ i prelazimo na sljedeću instrukciju~\eqref{d:54}.
\begin{gather*}
%\SwapAboveDisplaySkip
\label{d:51}\tag{$\delta$3e}
    \delta_{(j)}(s_i,\t\textbullet):=(s_i,\t\textbullet,1)\\
\label{d:52}\tag{$\delta$3f}
    \delta_{(j)}(s_i,\t\textopenbullet):=(t_i,\t\textopenbullet,-1)\\
\label{d:53}\tag{$\delta$3g}
    \delta(t_i,\t\#):=(p_l,\t\#,1)\\
\label{d:54}\tag{$\delta$3h}
    \delta_{(j)}(t_i,\t\textbullet):=(p_{i+1},\t\textopenbullet,-1)
\end{gather*}
	Ako je $I_i$ tipa $\goto$, recimo $i.\;\goto\;l$, samo odemo na pripremu za instrukciju $I_l$~\eqref{d:61}.
\begin{equation*}
\label{d:61}\tag{$\delta$3i}
    \delta(s_i,\gamma):=(p_l,\gamma,-1)\text{, za sve $\gamma\in B^m$}
\end{equation*}
	Lako je vidjeti da je pozicija ulaskom u $p_{i'}$ doista veća ili jednaka $k$ --- recimo, primjenom~\eqref{d:54} pozicija će biti $k+c(\reg j)-1\ge k$, jer je u tom slučaju $c(\reg j)>0$ --- dakle, postignuta konfiguracija jest $m$-reprezentacija od $d$.
%Sada samo još treba na svako stanje oblika $p_{i'}$ "našarafiti" konstrukciju iz leme~\ref{lm:pi>si}. Pozicija u svakom od tih stanja je strogo veća od $k$, ako je na početku u stanju $s_i$ bila $k+2$; recimo primjenom~\eqref{d:53} će pozicija biti upravo $k+2>k$, a primjenom~\eqref{d:54} će biti $k+c(\reg j)$, što je veće od $k$ jer je u tom slučaju $c(\reg j)>0$.
\end{proof}

%Radi jednostavnosti, pretpostavit ćemo da za svaku instrukciju (i još za $i=n$) imamo sva tri stanja $s_i$, $p_i$ i $t_i$ --- iako će stanja $t_i$ biti povezana s ostalim stanjima samo ako je instrukcija s rednim brojem $i$ tipa $\dec$; inače će biti nedostupna i ni na koji način neće utjecati na $\mathcal T_0$-izračunavanje. Nećemo ih ni crtati na dijagramima (baš kao ni stanje greške $q_x$), ali tako će formalna definicija biti jednostavnija.

Tipove fragmenata iz dokaza možemo prikazati dijagramima:
\begin{itemize}
    \item[$\rhd$]\quad $i.\;\incr j$\;:\quad
\begin{tikzpicture}[baseline=(si)]
\node[state] (pi) {$p_i$};
\node[state, right of=pi] (si) {$s_i$};
\node[state, right of=si] (pi1) {$p_{\!i\!+\!1}$};
\draw
(pi) edge[loop left,dashed] node[left]{$B^m$} (pi)
(pi) edge[above] node{$\t\#$} (si)
(si) edge[loop below] node[above right,xshift=4]{\t\textbullet\,\texttt@$j$} (si)
(si) edge[dashed] node[above]{\t\textopenbullet:\t\textbullet\,\texttt@$j$} (pi1)
;
\end{tikzpicture}
\vspace{-1.5cm}
    \item[$\rhd$]\quad $i.\;\decr jl$\;:\quad
\begin{tikzpicture}[baseline=(si)]
\node[state] (pi) {$p_i$};
\node[state, right of=pi] (si) {$s_i$};
\node[state, right of=si] (ti) {$t_i$};
\node[state, below right=0.5 and 2 of ti] (pl) {$p_l$};
\node[state, above right=0.5 and 2 of ti] (pi1) {$p_{\!i\!+\!1}$};
\draw
(pi) edge[loop left,dashed] node[left]{$B^m$} (pi)
(pi) edge[above] node{$\t\#$} (si)
(si) edge[loop below] node[above right,xshift=4]{\t\textbullet\,\texttt@$j$} (si)
(si) edge[dashed] node[above]{\t\textopenbullet\,\texttt@$j$} (ti)
(ti) edge node[above]{\t\#} (pl)
(ti) edge[dashed] node[above,xshift=-6]{\t\textbullet:\t\textopenbullet\,\texttt@$j$} (pi1)
;
\end{tikzpicture}
\vspace{-0.8cm}
    \item[$\rhd$]\quad $i.\;\goto\;l$\;:\qquad\quad
\begin{tikzpicture}[baseline=(si)]
\node[state] (pi) {$p_i$};
\node[state, right of=pi] (si) {$s_i$};
\node[state, right of=si] (pl) {$p_l$};
\draw
(pi) edge[loop left,dashed] node[left]{$B^m$} (pi)
(pi) edge[above] node{$\t\#$} (si)
(si) edge[dashed] node[above]{$B^m$} (pl)
;
\end{tikzpicture}
\end{itemize}

%\subsection{Prepoznavanje završne konfiguracije}
\begin{propozicija}[{name=[treći fragment transpiliranog stroja]}]\label{pp:faza3}
	%Neka RAM-algoritam $P^1$ širine $m$ računa funkciju $\f f^1$. Tada 
	Postoji fragment Turingova stroja koji za sve $x\in\N$, počevši od bilo koje $m$-reprezentacije početne $\mathcal S_0$-konfiguracije s ulazom $x$, dostigne neku $m$-reprezentaciju završne $\mathcal S_0$-konfiguracije $P_0$-izračunavanja s $x$ ako je $x\in\dom{\N\varphi_0}$, a inače nikada ne stigne u stanje $p_n$.
\end{propozicija}
\begin{proof}
	Za svaki $x\in\N$, označimo sa $(c_l)_{l\in\N}$ $P_0$-izračunavanje s $x$ i indukcijom po $l$ dokažimo da dosad sastavljeni fragment Turingova stroja dostigne $m$-reprezentaciju od $c_l$. Baza je očita, jer je $c_0$ upravo početna konfiguracija. %Baza je primjena lema~\ref{lm:faza1} i~\ref{lm:faza2}, kako je ilustrirano u~\eqref{eq:+afaze}. 
	Korak (ako $c_l$ nije završna) je primjena leme~\ref{lm:gadgets}. Dakle, ako $P_0$-izračunavanje stane u $l_0$ koraka, fragment će postići $m$-reprezentaciju završne konfiguracije $c_{l_0}$, došavši u stanje $p_n$.

No vrijedi i obrat: pri simulaciji jednog RAM-prijelaza $c\leadsto d$, fragment posjećuje samo stanja $p_i$, $s_i$ i $t_i$ za $i=c(\textsc{pc})$ ili za $i=d(\textsc{pc})$. Dakle, jedini način da dođe u stanje $p_n$ je da doista neka RAM-konfiguracija u izračunavanju preslika \textsc{pc} u $n$, što znači da $P$-izračunavanje s $x$ stane.
\end{proof}

%Općenito, ovaj dio je na neki način najkompliciraniji (zbog broja stanja --- za tipični RAM-program ovaj fragment će biti višestruko veći od čitavog ostatka stroja $\mathcal T_0$; a i zbog činjenice da ne mora stati, odnosno doći u stanje $p_n$). S druge strane, možemo reći i da je najjednostavniji, jer ima vrlo uniformnu strukturu: fragmentići (u simulacijama obično se zovu \emph{gadgets}) za pojedine instrukcije su jednostavni i lijepo se slažu. Pogledajmo jednostavni primjer.

%\begin{korolar}[{name=[prve tri faze transpiliranog stroja]}]\label{kor:faza3}
	%Dosad izgrađeni Turingov stroj (sastavljen od prva tri fragmenta) dostigne stanje $p_n$ ako i samo ako je pokrenut s ulazom $w\in\dom{\varphi_0}$, i u tom trenutku na traci nakon $\t\#$ u tragu $0$ piše $\raisebox{-1pt}{\t\textbullet}^y\raisebox{-1pt}{\t\textopenbullet}\dotsm$, gdje je $y=\N\varphi_0(\kr w)=\kr{\varphi_0(w)}$.
%\end{korolar}
%\begin{proof}
    %Primijenimo propoziciju~\ref{pp:faza3} na RAM-program $P_0$ ($f=\N\varphi_0$) i $x:=\kr w$. % i $k:=\dulj{w}$. %Štoviše, jer se $f$ računa na $x$ koji jest kod, dovoljno je zahtijevati $f\approx\N\varphi_0$.
%\end{proof}

\begin{primjer}[{name=[treći fragment transpiliranog stroja]}]\label{pr:+a2}
U primjeru~\ref{pr:+a} smo vidjeli RAM-program $P_{\t a}$~\eqref{eq:+aprog} duljine $4$ i širine $2$, koji računa prateću funkciju dopisivanja \t a na kraj riječi, $\N\varphi_{\t a}(x):=2x+1$.

Treći fragment Turingova stroja koji odgovara $P_{\t a}$ prikazan je dijagramom
\begin{equation}
\hspace{-2.7cm}
\begin{tikzpicture}[baseline=(s3)]
\node[state]                 (p0) {$p_0$};
\node[state,right of=p0]     (s0) {$s_0$};
%\node[state,right of=s0]     (t0) {$t_0$};
\node[state,below=1.5 of p0] (p1) {$p_1$};
\node[state,below=1.5 of s0] (s1) {$s_1$};
\node[state,right of=s1] (t1) {$t_1$};
\node[state,below=1.5 of p1] (p2) {$p_2$};
\node[state,below=1.5 of s1] (s2) {$s_2$};
\node[state,below=1.5 of t1] (p4) {$p_4$};
\node[state,below=1.5 of p2] (p3) {$p_3$};
\node[state,below=1.5 of s2] (s3) {$s_3$};
%\node[state,below=1.5 of p4] (s4) {$s_4$};
%\node[state,below=1.5 of t3] (t4) {$t_4$};
%\node[state,below=1.5 of p4] (p5) {$p_5$};
%\node[state,below=1.5 of s4] (s5) {$s_5$};
%\node[state,below=1.5 of t4] (t5) {$t_5$};
\node[left=4 of p0,align=left] {$0.\;\incr0\;:$};
\node[left=4 of p1,align=left] {$1.\;\decr14\;:$};
\node[left=4 of p2,align=left] {$2.\;\incr0\;:$};
\node[left=4 of p3,align=left] {$3.\;\goto\;0\;:$};
%\node[left=4 of p4,align=left] {$4.\;\incr0\;:$};
\draw
(p0) edge[loop left,dashed] node[left] {$B^2$} (p0)
(p1) edge[loop left,dashed] node[left] {$B^2$} (p1)
(p2) edge[loop left,dashed] node[left] {$B^2$} (p2)
(p3) edge[loop left,dashed] node[left] {$B^2$} (p3)
%(p4) edge[loop right,dashed] node[right] {$B^2$} (p4)
(p0) edge node[above] {$\t\#$} (s0)
(p1) edge node[above] {$\t\#$} (s1)
(p2) edge node[below] {$\t\#$} (s2)
(p3) edge node[below] {$\t\#$} (s3)
%(p4) edge node[right] {$\t\#$} (s4)
(s0) edge[loop right] node[right] {\t\textbullet\,\texttt@$0$} (s0)
(s1) edge[loop above] node[above] {\t\textbullet\,\texttt@$1$} (s1)
(s2) edge[loop right] node[right] {\t\textbullet\,\texttt@$0$} (s2)
(s1) edge[dashed] node[above] {\t\textopenbullet\,\texttt@$1$} (t1)
(t1) edge[dashed] node[above left,yshift=-3,pos=0.6] {\t\textbullet:\t\textopenbullet\,\texttt@$1$} (p2)
(s0) edge[dashed] node[above left,yshift=-3] {\t\textopenbullet:\t\textbullet\,\texttt@$0$} (p1)
(s2) edge[dashed] node[below right,yshift=5,pos=0.4] {\t\textopenbullet:\t\textbullet\,\texttt@$0$} (p3)
(s3) edge[dashed,out=160,in=220,looseness=2] node[right,pos=0.6] {$B^2$} (p0)
%(t1) edge[out=267,in=20,looseness=1.5] node[right] {\t\#} (p4)
(t1) edge node[right] {\t\#} (p4)
;
\end{tikzpicture}\text{\hspace{-2.7cm}.%\,\qedhere%
}
\end{equation}
$P_{\t a}$-izračunavanje s $\kr{\t{ab}}=4$ je %($c$ skraćeno zapisujemo kao $c(\reg0)c(\reg1)c(\textsc{pc})$)
%\begin{multline}
        %040\leadsto
	%141\leadsto
	%132\leadsto
	%233\leadsto
	%230\leadsto
	%331\leadsto
        %322\leadsto
	%423\leadsto
	%420\leadsto
	%521\leadsto
	%512\leadsto{}\\{}\leadsto
	%613\leadsto
        %610\leadsto
	%711\leadsto
	%702\leadsto
	%803\leadsto
	%800\leadsto
	%901\leadsto
        %904\lcirclearrowleft
%\end{multline}
	\begin{equation}
\begin{array}{r|rrrrrrrrrrrrrrrrrrrr}
i&\;0&1&2&3&4&5&6&7&8&9&\!10&\!11&\!12&\!13&\!14&\!15&\!16&\!17&\!18&\dotsm\\\hline
c_i(\reg0)&
0&0&1&2&2&2&3&4&4&4&5&6&6&6&7&8&8&8&9&9\\
c_i(\reg1)&
4&3&3&3&3&2&2&2&2&1&1&1&1&0&0&0&0&0&0&0\\
c_i(\reg2..)&
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\
c_i(\textsc{pc})&
0&1&2&3&0&1&2&3&0&1&2&3&0&1&2&3&0&4&5&5
\end{array}
	\end{equation}
	s izlaznim podatkom $9=2\cdot\mspace{1mu}4+1$, i odgovara mu šetnja kroz $2$-reprezentacije %Turing-konfiguracije %(ne pišemo, svima zajednički, početak \t{\renewcommand{\arraystretch}{0.1}\$\boo\boo\#})
    %$P_{\t a}$-izračunavanju s $\kr{\t{ab}}=4$, s izlaznim podatkom $9=2\cdot4+1$, po preslikavanju $Turing_{224}$ odgovara šetnja kroz Turing-konfiguracije
\begin{multline}\label{eq:+a2}
\renewcommand{\arraystretch}{0.1}
\T{\$\boo\boo\#}{\mund{p_{\!0}}}{\boi}{\boi\boi\boi}\leadsto^*
\T{\$\boo\boo}{\mund{p_{\!1}}}{\vphantom\boo\#}{\bii\boi\boi\boi}\leadsto^*
\T{\$\boo\boo\#\bii\boi}{\mund{p_{\!2}}}{\boi}{}\leadsto^*
\T{\$\boo\boo\#}{\mund{p_{\!3}}}{\bii}{\bii\boi}\leadsto^*
\T{\$\boo\boo}{\mund{p_{\!0}}}{\vphantom\boo\#}{\bii\bii\boi}\leadsto^*
\T{\$\boo\boo\#\bii}{\mund{p_{\!1}}}{\bii}{\bii}\leadsto^*
{}\\{}\leadsto^*
\renewcommand{\arraystretch}{0.1}
\T{\$\boo\boo\#\bii}{\mund{p_{\!2}}}{\bii}{\bio}\leadsto^*
\T{\$\boo\boo\#\bii\bii}{\mund{p_{\!3}}}{\bio}{\bio}\leadsto^*
\T{\$\boo\boo}{\mund{p_{\!0}}}{\vphantom\boo\#}{\bii\bii\bio\bio}\leadsto^*
\T{\$\boo\boo\#\bii\bii\bio}{\mund{p_{\!1}}}{\bio}{\bio}\leadsto^*
\T{\$\boo\boo\#}{\mund{p_{\!2}}}{\bii}{\bio\bio\bio\bio}\leadsto^*
{}\\{}\leadsto^*
\renewcommand{\arraystretch}{0.1}
\T{\$\boo\boo\#\bii\bio\bio\bio}{\mund{p_{\!3}}}{\bio}{\bio}\leadsto^*
\T{\$\boo\boo}{\mund{p_{\!0}}}{\vphantom\boo\#}{\bii\bio\bio\bio\bio\bio}\leadsto^*
\T{\$\boo\boo\#\bii\bio\bio\bio\bio}{\mund{p_{\!1}}}{\bio}{\bio}\leadsto^*
\T{\$\boo\boo}{\mund{p_{\!2}}}{\vphantom\boo\#}{\bio\bio\bio\bio\bio\bio\bio}\leadsto^*
{}\\{}\leadsto^*
\renewcommand{\arraystretch}{0.1}
\T{\$\boo\boo\#\bio\bio\bio\bio\bio\bio}{\mund{p_{\!3}}}{\bio}{\bio}\leadsto^*
\T{\$\boo\boo}{\mund{p_{\!0}}}{\vphantom\boo\#}{\bio\bio\bio\bio\bio\bio\bio\bio}\leadsto^*
\T{\$\boo\boo\#\bio\bio\bio\bio\bio\bio\bio}{\mund{p_{\!1}}}{\bio}{\bio}\leadsto^*
\T{\$\boo\boo\#}{\mund{p_{\!4}}}{\bio}{\bio\bio\bio\bio\bio\bio\bio\bio}
\,\text,
\end{multline}
koja predstavlja prirodni nastavak one u~\eqref{eq:+afaze}.
\end{primjer}

%\begin{napomena}[{name=[zaustavljanje transpiliranog stroja ovisi samo o trećoj fazi]}]\label{nap:snstane}
%Ostatak Turingova stroja koji konstruiramo vezat će se s dosad izgrađenim dijelom isključivo kroz stanje $p_n$, a njegov rad će uvijek stati, pa ćemo na kraju moći zaključiti da čitav Turingov stroj stane ako i samo ako dođe u stanje $p_n$, odnosno ako i samo ako je ulazna riječ u domeni od $\varphi_0$.
%\end{napomena}

%Time smo riješili pitanje domene, i 
Još je potrebno dekodirati $y$ (ako postoji) u riječ $v:=\varphi_0(w)$ i postaviti je na početak trake.
%\subsection{Dekodiranje izlazne vrijednosti}
Postupak je sličan onome u drugoj fazi, samo u obrnutom smjeru. Imamo broj $y$ zapisan unarno (pomaknuta baza~$1$) u tragu $0$, a trebamo ga zapisati u pomaknutoj bazi $b$ --- skidajući po jedan \t\textbullet\ iz traga $0$ i inkrementirajući riječ iz $\Sigma_0^*$ svaki put. Ipak, nekoliko tehničkih detalja čine ovaj postupak kompliciranijim.

Prvo, umjesto pisanja konstantnog znaka $r_1\in B^m$, morat ćemo čitati bilo koji znak koji u tragu $0$ ima \t\textbullet. Srećom, to nam upravo omogućuje definicija~\ref{def:trag}.

Drugo i važnije, kod dekrementiranja smo znali da riječ neće postati dulja, pa smo prazninama skraćivali zapis broja koliko je već potrebno, dok ga nismo dekrementirali sasvim do nule. Kod inkrementiranja nemamo unaprijed određenu gornju granicu za duljinu izlazne riječi $v:=\varphi_0(w)$, pa ćemo morati obrisati separator \t\# i koristiti čitavu traku za njenu konstrukciju. Ipak, već upotrijebljeni dio trake će biti dovoljan, jer sadrži barem barem $y=\kr{\varphi_0(w)}$ znakova \t\textbullet\ u tragu $0$.

\begin{lema}[{name=[duljina riječi nije veća od koda riječi]}]\label{lm:dulj<=kr}
Za svaku riječ $w$ vrijedi $\dulj w\le\kr w$.
\end{lema}
\begin{proof}
Označimo s $b$ broj znakova abecede $\Sigma$ nad kojom je riječ $w$.
	Svaki pribrojnik u sumi~\eqref{eq:kodNSz} je pozitivan, jer je svaka znamenka $\N\Sigma(\alpha_i)\in[1\mspace{-1mu}\dd b]$ te je $b>0$ zbog $\Sigma\ne\emptyset$. Dakle, svaki pribrojnik je barem $1$, pa je suma veća ili jednaka broju pribrojnika. No suma je po definiciji $\kr w$, a broj pribrojnika je upravo $\dulj w$.

Za $b=1$ vrijedi jednakost (jer je jedina moguća znamenka $1$).
\end{proof}

Štoviše, lema~\ref{lm:dulj<=kr} pokazuje da riječ možemo dekodirati korak po korak: u svakom trenutku će nam u tragu $0$ ostati $y'$ znakova \t\textbullet, a desno od početnog graničnika će biti napisana riječ $u'$ čiji je kod $\kr{u'}=y-y'$, pa će sigurno stati u prostor od $k+y-y'\ge y-y'$ ćelija oslobođen skidanjem $y-y'$ znakova \t\textbullet.

\subsection{Konstrukcija izlazne riječi}

\begin{lema}[{name=[četvrti fragment transpiliranog stroja]}]\label{lm:faza4}
Postoji fragment Turingova stroja koji prevodi bilo koju $m$-reprezentaciju završne konfiguracije $(p_n,k,\t\$\bl^{\dulj w}\t\#t\bl\ldots)$, gdje je $k>\dulj w$ i $t$ u tragu $0$ ima oblik $\t\textbullet^y\t\textopenbullet^{\dulj t-y}$, u konfiguraciju $(l_\bl,\dulj v,\t\$v\bl\ldots)$, gdje je $\kr v=y$.% te $u\in(B^m)^*$.
\end{lema}

\begin{proof}
%Kao što rekosmo, dokaz je sličan dokazu leme~\ref{lm:faza2}, samo u suprotnom smjeru. 
Prvo odemo do kraja upotrijebljenog dijela trake~\eqref{d:4a} i tamo zapišemo krajnji graničnik~\eqref{d:4b}. Zatim odemo do početka trake~\eqref{d:4c}, brišući pritom separator~\eqref{d:4d}. Tada se okrenemo~\eqref{d:4e} i idemo desno kroz znakove s \t\textopenbullet\ u tragu $0$~\eqref{d:4f} --- dok ne dođemo do prvog \t\textbullet, koji obrišemo~\eqref{d:4g} i prenesemo lijevo~\eqref{d:4h} do prvog znaka iz $\Sigma_0$. Ako je taj znak "najveći", zamjenjujemo ga "najmanjim"~\eqref{d:4i} i nastavljamo ići lijevo, sve dok ne dođemo do nekog znaka koji možemo "inkrementirati"~\eqref{d:4j}, ili do početnog graničnika~\eqref{d:4k}. U ovom posljednjem slučaju, odemo na kraj riječi koja se mora sastojati samo od znakova $\alpha_1$~\eqref{d:4l} i dopišemo još jedan na kraj~\eqref{d:4m}. Odemo po novi~\t\textbullet\ iz traga $0$\dots\ kada ih sve potrošimo odlazimo lijevo brišući krajnji graničnik i sve ostatke izračunavanja s trake~\eqref{d:4n}, dok ne udarimo u zadnji znak od $v$ (ili početni graničnik ako je $v=\varepsilon$).

%Zatim se krećemo ulijevo kroz znakove \t\textopenbullet\ u tragu $0$~\eqref{
%Prvo odemo do kraja upotrijebljenog (nepraznog) dijela trake~\eqref{d:71} i tamo zapišemo krajnji graničnik~\eqref{d:72}. Zatim se krećemo ulijevo kroz znakove \t\textopenbullet\ u tragu $0$~\eqref{d:73} dok ne dođemo do \t\textbullet, koji maknemo~\eqref{d:74} i prenosimo ga desno kroz "znamenke" i "stupce bitova"~\eqref{d:75}, dok ne dođemo do krajnjeg graničnika~\eqref{d:76}. Tada se opet krećemo ulijevo inkrementirajući riječ: zamjenjujući "devetke jedinicama"~\eqref{d:77} te inkrementirajući prvu "ne-devetku"~\eqref{d:78}, ili ako takve nema, dodajući "jedinicu" slijeva~\eqref{d:79}. Zatim prođemo kroz ostale znamenke do "praznog prostora"~\eqref{d:70} i opet izvršavamo cijeli postupak dok ne dođemo do separatora \t\#.
	Argument zašto to funkcionira je praktički isti kao u dokazu leme~\ref{lm:faza2}: nakon svakog "prolaza kroz petlju" imamo traku oblika $\t{\$}ut\t{\$}$ pri čemu $t$ ima $\kr v-\kr u$ znakova \t\textbullet\ u tragu $0$. Na početku je $u=\varepsilon$ pa je to istina ($\kr v-\kr\varepsilon=y-0=y$), svakim prolazom ostaje istina jer se $\kr u$ povećava za $1$ dok se broj znakova \t\textbullet\ u tragu $0$ smanjuje za $1$ --- pa na izlasku iz petlje mora biti $\kr v-\kr u=0$, odnosno zbog injektivnosti kodiranja riječi $u=v$. Još je samo preostalo isprazniti i ostale tragove iz $t$ te obrisati zadnji \t\$.
%Jedina bitna razlika je što je tamo~\eqref{dia:T2} "radni ciklus" imao dva stanja ($q_0$ i $q_1$), a ovdje ih ima tri ($q_3$, $q_4$ i $q_5$). To je posljedica toga da inkrementiramo "s pogrešne strane", odnosno prenosimo kružiće slijeva nadesno, a kod kretanja zdesna nalijevo moramo pamtiti tražimo li tek znamenku koju ćemo inkrementirati (da bismo zamijenili "devetke jedinicama"), ili smo to već učinili (pa ostavljamo "devetke" na miru).
\end{proof}
\noindent\begin{gather*}
%\SwapAboveDisplaySkip
\label{d:4a}\tag{$\delta$4a}\delta(p_n,\gamma):=(p_n,\gamma,1)\text{, za sve }\gamma\in\{\t\#\}\cup B^m\setminus\{\bl\}\\
\label{d:4b}\tag{$\delta$4b}\delta(p_n,\bl):=(q_3,\t\$,-1)\\
\label{d:4c}\tag{$\delta$4c}\delta(q_3,\gamma):=(q_3,\gamma,-1)\text{, za sve }\gamma\in B^m\\
\label{d:4d}\tag{$\delta$4d}\delta(q_3,\t\#):=(q_3,\bl,-1)\\
\label{d:4e}\tag{$\delta$4e}\delta(q_3,\t\$):=(q_4,\t\$,1)\\
\label{d:4f}\tag{$\delta$4f}\delta_{(0)}(q_4,\t\textopenbullet):=(q_4,\t\textopenbullet,1)\\
\label{d:4g}\tag{$\delta$4g}\delta_{(0)}(q_4,\t\textbullet):=(q_5,\t\textopenbullet,-1)\\
\label{d:4h}\tag{$\delta$4h}\delta(q_5,\gamma):=(q_5,\gamma,-1)\text{, za sve }\gamma\in B^m\\
\label{d:4i}\tag{$\delta$4i}\delta(q_5,\alpha_b):=(q_5,\alpha_1,-1)\\
	\label{d:4j}\tag{$\delta$4j}\delta(q_5,\alpha_t):=(q_4,\alpha_{t+1},1)\text{, za sve }t\in[1\mspace{-1mu}\dd b\rangle\\
\label{d:4k}\tag{$\delta$4k}\delta(q_5,\t\$):=(q_6,\t\$,1)\\
\label{d:4l}\tag{$\delta$4l}\delta(q_6,\alpha_1):=(q_6,\alpha_1,1)\\
\label{d:4m}\tag{$\delta$4m}\delta(q_6,\gamma):=\delta(q_4,\alpha_1):=(q_4,\alpha_1,1)\text{, za sve }\gamma\in B^m\\
\label{d:4n}\tag{$\delta$4n}\delta(q_4,\t\$):=\delta(l_\bl,\gamma):=(l_\bl,\bl,-1)\text{, za sve }\gamma\in B^m
	%\label{d:71}\tag{$\delta$4a}\delta(p_n,\gamma):=(p_n,\gamma,1)\text{, za sve } \gamma\in \{\t\#\}\cup B^m\setminus\{\bl\}\\
%\label{d:72}\tag{$\delta$4b}\delta(p_n,\bl):=(q_3,\t\$,-1)\\
%\label{d:73}\tag{$\delta$4c}\delta_{(0)}(q_3,\t\textopenbullet):=(q_3,\t\textopenbullet,-1)\\
%\label{d:74}\tag{$\delta$4d}\delta_{(0)}(q_3,\t\textbullet):=(q_4,\t\textopenbullet,1)\\
%\label{d:75}\tag{$\delta$4e}\delta(q_4,\alpha):=(q_4,\alpha,1)\text{, za sve }\alpha\in\Sigma_0\dcup B^m\\
%\label{d:76}\tag{$\delta$4f}\delta(q_4,\t\$):=(q_5,\t\$,-1)\\
%\label{d:77}\tag{$\delta$4g}\delta(q_5,\alpha_b):=(q_5,\alpha_1,-1)\\
%\label{d:78}\tag{$\delta$4h}\delta(q_5,\alpha_t):=(q_3,\alpha_{t+1},-1)\text{, za sve }t\in[1\mspace{-1mu}\dd b\rangle\\
%\label{d:79}\tag{$\delta$4i}\delta(q_5,\gamma):=(q_3,\alpha_1,-1)\text{, za sve }\gamma\in B^m\\
%\label{d:70}\tag{$\delta$4j}\delta(q_3,\alpha):=(q_3,\alpha,-1)\text{, za sve }\alpha\in\Sigma_0
\end{gather*}
\begin{primjer}[{name=[četvrti fragment transpiliranog stroja]}]
Za $\Sigma_0:=\{\t a,\t b,\t c,\t d\}$, četvrti fragment možemo prikazati dijagramom
\begin{equation}
\begin{tikzpicture}[baseline=(q6)]\label{dia:T4}
%\clip (-1,-2.53) rectangle (8.5,2.16);
\node[state] (pn) {$p_n$};
\node[state,right of=pn] (q3) {$q_3$};
\node[state,right of=q3] (q4) {$q_4$};
\node[state,below of=q4] (q5) {$q_5$};
\node[state,right of=q5] (q6) {$q_6$};
\node[state,right of=q4] (lb) {$l_\bl$};
\draw
(pn) edge[loop above] node[right,xshift=7,yshift=-6] {$\t\#,{B^m}_+$} (pn)
(q3) edge[dashed,loop above] node[right,xshift=7,yshift=-6] {\t\#:\bl$\,,B^m$} (q3)
(q4) edge[loop above] node[right,xshift=7,yshift=-6] {$\t\textopenbullet\,\texttt@0,\t a$} (q4)
(lb) edge[loop above,dashed] node[right,xshift=7,yshift=-6] {$B^m$:\bl} (lb)
(pn) edge[dashed] node[below] {\bl:\t\$} (q3)
(q4) edge[dashed,left,bend right=35] node[left,xshift=-2,yshift=1] {\t\textbullet:\t\textopenbullet\,\texttt@$0$} (q5)
(q6) edge[loop right] node[right,align=left] {\t a} (q6)
(q5) edge node[above] {\t\$} (q6)
(q5) edge[dashed,loop left] node[left,align=right] {\t d:\t a$,B^m$} (q5)
(q5) edge node[right,align=left,yshift=-3] {\t a:\t b\\ \t b:\t c\\ \t c:\t d} (q4)
(q6) edge node[right,xshift=3] {$B^m$:\t a} (q4)
(q3) edge node[below] {\t\$} (q4)
(q4) edge[dashed] node[below] {\t\$:\bl} (lb)
;
\end{tikzpicture}\text{\;.\qedhere}
\end{equation}
\end{primjer}

%Zbog $\kr v=y=\kr{\varphi_0(w)}$ i propozicije~\ref{pp:bijkr} zapravo vrijedi $v=\varphi_0(w)$, odnosno (ako uopće dođemo u situaciju da možemo primijeniti lemu~\ref{lm:faza4}) već imamo izlaznu riječ na traci. Još je treba premjestiti na početak i obrisati sve ostalo s trake.

% \subsection{Pospremanje za sobom}

\begin{korolar}[{name=[peti fragment transpiliranog stroja]}]\label{kor:faza5}
Postoji fragment Turingova stroja koji prevodi konfiguraciju $(l_\bl,\dulj v,\t\$v\bl\ldots)$\\ u završnu konfiguraciju $(l_{\t\$},0,v\bl\ldots)$.
\end{korolar}
\begin{proof}
Samo treba pomaknuti čitavu izlaznu riječ za jednu ćeliju ulijevo, brišući početni graničnik --- drugim riječima, napraviti suprotno od%onog što prvi fragment (bez zadnjeg koraka) radi. Obrtanjem
~\eqref{d:10}:
\begin{equation*}
\label{d:50}\tag{$\delta$5}\delta(l_\beta,\alpha):=(l_\alpha,\beta,-1)\text{, za sve }\alpha\in\Sigma_0\dcup\{\t\$\}\text{, }\beta\in\Sigma_0\dcup\{\bl\}\text{.\;\qedhere}
\end{equation*}
\end{proof}

%Prvi korak je brisanje svih ostataka izračunavanja i separatora, tako da na traci ostanu jedino izlazna riječ $v$ i dva graničnika --- početni i krajnji~\eqref{d:81}. Time dobivamo konfiguraciju $(q_6,l+1,\t\$\bl^l\,v\t\$\bl\ldots)$, gdje je $l:=\dulj w+\dulj u+1$.

%Drugi korak je uzimanje jednog po jednog znaka od $v$ i njegov prijenos na početak trake~\eqref{d:83} --- s tim da će prvi znak od $v$ naići na početni graničnik i prebrisati ga~\eqref{d:86}, a svaki sljedeći znak će naići na onaj prije njega koji je već prenesen~\eqref{d:85} i zapisati se desno od njega~\eqref{d:86}. Time dobijemo konfiguraciju $(q_6,l+\dulj v+1,v\bl^{l+1}\t\$\bl\ldots)$ ako je $v\ne\varepsilon$. Za $v=\varepsilon$, ovog koraka nema, odnosno odmah smo u konfiguraciji $(q_6,l+1,\t\$\bl^l\t\$\bl\ldots)$.

%Treći korak počinje čitanjem i brisanjem završnog graničnika \t\$ i nastavlja prolaskom kroz praznine ulijevo~\eqref{d:83}, sve dok ne udarimo u zadnji znak od $v$ ako je $v\ne\varepsilon$~\eqref{d:85}, odnosno u početni graničnik (koji tada treba obrisati, ostavivši traku sasvim praznom) u slučaju $v=\varepsilon$~\eqref{d:89}.

    %Za nepraznu riječ $v$, završna će pozicija biti neposredno iza zadnjeg znaka od $v$, dakle $\dulj{v}$. Za praznu riječ, prijelaz~\eqref{d:89} će se dogoditi na lijevom rubu trake, pokušati pomak lijevo i ostati na istoj poziciji $0=\dulj{\varepsilon}=\dulj{v}$. U svakom slučaju dobili smo stanje $l_{\t\$}$, traku $v\bl\ldots$ i poziciju $\dulj{v}$.
%\end{proof}

%\noindent\begin{gather*}
    %\SwapAboveDisplaySkip
%\label{d:81}\tag{$\delta$5}\delta(q_3,\t\#):=\delta(q_6,\gamma):=(q_6,\bl,1)\text{, za sve }\gamma\in B^m\\
    %\label{d:83}\tag{$\delta$5b}\delta(q_6,\alpha):=\delta(m_\alpha,\bl):=(m_\alpha,\bl,-1)\text{, za sve }\alpha\in\Sigma_0\dcup\{\t\$\}\\
    %\label{d:85}\tag{$\delta$5c}\delta(m_\alpha,\beta):=(l_\alpha,\beta,1)\text{, za sve }\alpha\in\Sigma_0\dcup\{\t\$\},\beta\in\Sigma_0\\
%\label{d:86}\tag{$\delta$5d}\delta(m_\alpha,\t\$):=\delta(l_\alpha,\bl):=(q_6,\alpha,1)\text{, za sve }\alpha\in\Sigma_0\\
    %%\label{d:87}\tag{$\delta$5e}\delta(q_6,\t\$):=\delta(m_{\t\$},\bl):=(m_{\t\$},\bl,-1)\\
    %%\label{d:88}\delta(m_{\t\$},\alpha):=(l_{\t\$},\alpha,1)\text{, za sve }\alpha\in\Sigma_0\\
    %\label{d:89}\tag{$\delta$5e}\delta(m_{\t\$},\t\$):=(l_{\t\$},\bl,-1)
%\end{gather*}

%\begin{primjer}[{name=[peti fragment transpiliranog stroja]}]
%Za $\Sigma_0:=\{\t a,\t b\}$, peti fragment možemo prikazati dijagramom
%\begin{equation}\label{dia:T5}
%\begin{tikzpicture}[baseline=(q8)]
%\clip (-1,-2.53) rectangle (8.5,2.16);
%\node[state] (q5) {$q_3$};
%\node[state,below right of=q5] (q8) {$q_6$};
%\node[state,left of=q8] (ma) {$m_{\t a}$};
%\node[state,right of=q8] (mb) {$m_{\t b}$};
%\node[state,below left of=q8] (la) {$l_{\t a}$};
%\node[state,below right of=q8] (lb) {$l_{\t b}$};
    %\node[state,above right of=q8] (q9) {$m_{\t\$}$};
    %\node[state,accepting,right of=q9] (qz) {$l_{\t\$}$};
%\draw
%(q5) edge node[above,yshift=5] {\t\#:\bl} (q8)
%(q8) edge[loop above] node[above,yshift=-3] {$B^m$:\bl} (q8)
%(q8) edge[dashed,bend left] node[above] {\t a:\bl} (ma)
%(ma) edge[bend left] node[below,yshift=2] {\t\$:\t a} (q8)
%(q8) edge[dashed,bend right] node[above] {\t b:\bl} (mb)
%(mb) edge[bend right] node[below,yshift=2] {\t\$:\t b} (q8)
%(ma) edge[dashed,loop left] node[left] {\bl} (ma)
%(mb) edge[dashed,loop right] node[right] {\bl} (mb)
%(ma) edge node[left,xshift=2] {$\Sigma_0$} (la)
%(mb) edge node[right] {$\Sigma_0$} (lb)
%(la) edge node[below,xshift=3] {\bl:\t a} (q8)
%(lb) edge node[below,xshift=-3] {\bl:\t b} (q8)
%(q8) edge[dashed] node[right,xshift=1] {\t\$:\bl} (q9)
%(q9) edge[dashed,loop left] node[left] {\bl} (q9)
%(q9) edge[bend left] node[below] {$\Sigma_0$} (qz)
%(q9) edge[bend right,dashed] node[above] {\t\$:\bl} (qz)
%;
%\end{tikzpicture}\text.
%\end{equation}
%Za općenitu abecedu $\Sigma_0$, umjesto dva "viseća trokuta" ispod $q_6$, bit će ih $b$:\newline po jedan $\triangle q_6 m_\alpha l_\alpha$ za svaki znak $\alpha\in\Sigma_0$.
%\end{primjer}

%Stigli smo do završnog stanja $l_{\t\$}$. Time smo napokon završili konstrukciju Turingova stroja $\mathcal T_0$ i sve je spremno za dokaz "obrata" teorema~\ref{tm:tikp}.

%\subsection{Objedinjavanje}

\begin{teorem}[{name=[Turing-izračunljivost parcijalno rekurzivnih jezičnih funkcija]}]\label{tm:krit}
Neka je $\Sigma_0$ abeceda, $\N\Sigma_0$ njeno kodiranje te $\varphi_0$ funkcija nad njom.

Ako je $\N\varphi_0$ RAM-izračunljiva, tada je $\varphi_0$ Turing-izračunljiva.
\end{teorem}
\begin{proof}
Po pretpostavci postoji RAM-program $P_0$ koji računa $\N\varphi_0$.
	
	Označimo $n:=n_{P_0}$ i $m:=m_{P_0^1}$. Tvrdimo da tada funkciju $\varphi_0$ računa Turingov stroj
\begin{align}
    &\qquad\mathcal T_0:=(Q,\Sigma_0,\Gamma,\bl,\delta,n_{\t\$},l_{\t\$})\text,
\shortintertext{s komponentama}
    Q&:=\bdcup_{i\le6}\{q_i\}\dcup\bdcup_{i\le n}\{p_i,s_i,t_i\}\dcup\bdcup_{\mathclap{\alpha\in\Sigma_0\dcup\{\t\$,\mspace{1mu}\bl\}}}\,\{n_\alpha,l_\alpha\}\dcup\{q_x\}\text,\\
    \Gamma&:=\Sigma_0\dcup\{\t\$,\t\#\}\dcup B^m\text{, gdje je }B^m:=\prod\nolimits_{i<m}\{\t\textopenbullet,\t\textbullet\}\text,\\
    \bl&:=(\t\textopenbullet,\t\textopenbullet,\dotsc,\t\textopenbullet)^\intercal\in B^m\text{ (zapisana kao stupac),}
\end{align}
	i funkcijom prijelaza $\delta$ zadanom jednakostima~\eqref{d:10}--\eqref{d:50}, %($\delta\,\cdots$), %\eqref{d:11}--\eqref{d:12}, \eqref{d:21}--\eqref{d:28}, \eqref{d:31}--\eqref{d:61}, \eqref{d:71}--\eqref{d:70} i \eqref{d:81}--\eqref{d:89},
    tako da se svi parovi $(q,\alpha)\in(Q\setminus\{l_{\t\$}\})\times\Gamma$ nenavedeni u tim jednakostima preslikavaju u $(q_x,\alpha,-1)$.

Doista, neka je $w\in\Sigma_0^*$ proizvoljna riječ i označimo s $k:=\dulj{w}$ njenu duljinu.
	
	Promotrimo prvo slučaj kada je $w\in\dom{\varphi_0}$.

    Tada će početnu konfiguraciju $(n_{\t\$},0,w\bl\ldots)$ prvi fragment od $\mathcal T_0$ (lema~\ref{lm:faza1}) prebaciti u $(n_\bl,k+1,\t\$w\bl\ldots)$, a nju će pak drugi fragment prebaciti u $(p_0,k+2,\t\$\bl^k\,\t\#r_1^{\kr w}\bl\ldots)$, gdje je $r_1=(\t\textopenbullet,\t\textbullet,\t\textopenbullet,\dotsc,\t\textopenbullet)^\intercal$ (lema~\ref{lm:faza2}). Kako je $w\in\dom{\varphi_0}$, vrijedi $x:=\kr w\in\dom{\N\varphi_0}$, pa $P_0$-izračunavanje s $x$ stane, s izlaznim podatkom $y:=\N\varphi_0(x)=\kr{\varphi_0(w)}$. Prema propoziciji~\ref{pp:faza3}, $\mathcal T_0$-izračunavanje s $w$ (treća faza) će doći u konfiguraciju $(p_n,k',\t\$\bl^k\,\t\#t\bl\ldots)$, gdje je $k'>k$ i $t$ u tragu $0$ ima oblik $\t\textbullet^y\t\textopenbullet^{\dulj t-y}$. Tu će pak konfiguraciju četvrti fragment (lema~\ref{lm:faza4}) prebaciti u $(l_\bl,\dulj v,\t\$v\bl\ldots)$, gdje je $v:=\varphi_0(w)$. Peti će fragment (korolar~\ref{kor:faza5}) napokon tu konfiguraciju prevesti u završnu konfiguraciju $(l_{\t\$},0,v\bl\ldots)$, s izlaznom riječju $v=\varphi_0(w)$ na traci.
%Prikažimo postupak Turing-iz\-ra\-ču\-na\-va\-nja kroz faze: % (sa $z$ je označen najveći broj u ikojem relevantnom registru od $\mathcal S_0$ u završnoj konfiguraciji $P_0$-izračunavanja s $\kr w$):
\begin{equation}
\begin{array}{l|ccl}
			     &\text{stanje}&\text{pozicija}&\text{traka}\\\hline
\text{početna konfiguracija} & n_{\t\$} & 0         & w\bl\ldots \\
\text{nakon prve faze}       & n_\bl & \dulj w+1   & \t\$w\bl\ldots \\
\text{nakon druge faze}      & p_0 & \dulj w+2 & \t\$\bl^{\dulj w}\t\#r_1^{\kr w}\bl\ldots \\
\text{nakon treće faze}      & p_n & {}>\dulj w & \renewcommand{\arraystretch}{0.1}
    \t\$\bl^{\dulj w}\t\#\begin{array}{@{}c@{}}\t\textbullet\\?\end{array}^{\kr{v}}\begin{array}{@{}c@{}}\t\textopenbullet\\?\end{array}%^{z-\kr{v}}\bl
    \ldots\\
\text{međukorak četvrte faze} & q_4 & 1 & \renewcommand{\arraystretch}{0.1}\t\$\bl^{\dulj w+1}\begin{array}{@{}c@{}}\t\textbullet\\?\end{array}^{\kr v}\begin{array}{@{}c@{}}\t\textopenbullet\\?\end{array}\ldots\t\$\bl\ldots\\
\text{nakon četvrte faze}    %& q_3 & \dulj w+1 &
& l_\bl & \dulj v & \t\$v\bl\ldots\\
%\renewcommand{\arraystretch}{0.1}
%\t\$\bl^{\dulj w}\t\#\begin{array}{@{}c@{}}\t\textopenbullet\\?\end{array}^{z-\dulj v}v\t\$\bl\ldots\\
%\text{prvi korak pete faze} & q_6 & \dulj w+2+z-\dulj v       & \t\$\bl^{\dulj w+1+z-\dulj v}v\t\$\bl\ldots\\
%\text{drugi korak pete faze}& q_6 & \dulj w+2+z & v\bl^{\dulj w+2+z-\dulj v}\t\$\bl\ldots\\
    \text{završna konfiguracija} & l_{\t\$} & 0 & v\bl\ldots
\end{array}
\end{equation}

	Ako pak $w\notin\dom{\varphi_0}$, tada će se prve dvije faze izvršiti jednako, ali iz $x\notin\dom{\N\varphi_0}$ po definiciji~\ref{def:compute} slijedi da $P_0$-izračunavanje s $x$ nikad neće stati, pa po propoziciji~\ref{pp:faza3} niti $\mathcal T_0$-izračunavanje neće doći do $p_n$. %Prema napomeni~\ref{nap:snstane}, 
	To znači da ono nikad neće stati (doći do $l_{\t\$}$), jer svaki put od $n_{\t\$}$ do $l_{\t\$}$ vodi kroz stanje $p_n$.
\end{proof}

Uočimo sličnost provedenog postupka s dokazom propozicije~\ref{prop:semfmacro}. Tamo smo makro-stroju omogućili da u izoliranoj okolini izvrši neki konkretni RAM-program, a ovdje smo to omogućili Turingovu stroju. Kao i u makro-programu~\eqref{mprog:funmakro} iz definicije~\ref{def:funmakro}, postupak se sastoji od pet faza: "otvaranje okvira" pomicanjem udesno, prijenos (kodiranje) argumenata u simulaciju (konstrukcija početne konfiguracije), sama simulacija (izvršavanje pojedinih instrukcija RAM-programa) te, ako ona stane, prijenos (dekodiranje) njene povratne vrijednosti iz završne konfiguracije i "zatvaranje okvira" pomicanjem ulijevo.

\begin{primjer}[{name=[transpilirani stroj dodaje znak na kraj riječi]}]\label{pr:+a3}
Primjer~\ref{pr:+a} sad možemo pratiti kroz čitavo izračunavanje:
\begin{align}
	\text{početna konfiguracija}&&&\T{}{n_{\t\$}}{a}{b}\\[-1mm]
	\text{uokvirivanje ulaza}&&{}\leadsto^*{}&\T{\$a}{q_0}{b}{\#}\\[-1mm]
	\text{kodiranje ulaza: }\kr{\t{ab}}=(12)_2=4&&\leadsto^*{}&
\renewcommand{\arraystretch}{0.1}
	\T{\$\bl\bl\#}{\mund{p_0}}{\boi}{\boi\boi\boi}\\[-1mm]
	\text{računanje }2\cdot4+1=9\text{; raspisano u~\eqref{eq:+a2}}&&{}\leadsto^*{}&
\renewcommand{\arraystretch}{0.1}
	\T{\$\bl\bl\#}{\mund{p_4}}{\bio}{\bio\bio\bio\bio\bio\bio\bio\bio}\\[-1mm]
	\text{uokvirivanje izlaza}&&{}\leadsto^*{}&
\renewcommand{\arraystretch}{0.1}
	\T{\$}{q_4}{\bl}{\bl\bl\bio\bio\bio\bio\bio\bio\bio\bio\bio\t\$}\\[-1mm]
	\text{dekodiranje izlaza: }9=(121)_2=\kr{\t{aba}}&&{}\leadsto^*{}&
\renewcommand{\arraystretch}{0.1}
	\T{\$aba}{q_4}{\bl}{\bl\bl\bl\bl\bl\bl\bl\bl\$}\\[-1mm]
%\text{uokvirivanje izlaza}&&{}\leadsto^*{}&
%\renewcommand{\arraystretch}{0.1}
	%\T{\$\bl\bl\bl\bl\bl\bl\bl\bl\bl}{q_6}{a}{ba\$}\\[-1mm]
%\text{premještanje izlaza}&&{}\leadsto^*{}&
%\renewcommand{\arraystretch}{0.1}
%	\T{aba\bl\bl\bl\bl\bl\bl\bl\bl\bl\bl}{q_6}{\$}{}\\[-1mm]
\text{završna konfiguracija}&&{}\leadsto^*{}&
    \T{}{l_{\t\$}}{a}{ba}\lcirclearrowleft\text.
\end{align}

Dodati \t a na kraj riječi Turingov stroj očito može daleko jednostavnije --- ali ovaj primjer zapravo pokazuje kako može računati bilo koju funkciju čiju prateću funkciju RAM-stroj može računati. Suština računanja odvija se u primjeru~\ref{pr:+a2} --- ovo je samo hrpa "papirologije" prije i poslije, koju treba riješiti da bi taj primjer bio koristan.
\end{primjer}

Ukratko, dokazali smo da je za \emph{jezične} funkcije izračunljivost u jezičnom modelu jednako snažna kao izračunljivost njihovih pratećih funkcija u brojevnom modelu. Time smo napokon opravdali neovisnost o korištenom \emph{encodingu} i riješili "filozofski problem" proizvoljnosti znakova abecede. %s početka točke~\ref{sec:kSigma}.

\begin{korolar}[{name=[neovisnost izračunljivosti jezične funkcije o kodiranju abecede]}]\label{kor:ikojiNSigma}
Neka je $\Sigma$ abeceda te $\varphi$ jezična funkcija nad njom.

	Tada parcijalna rekurzivnost funkcije $\N\varphi$ ne ovisi o izboru kodiranja $\N\Sigma$.
\end{korolar}
\begin{proof}
Neka su $\N\Sigma$ i $\N'\Sigma$ dva kodiranja $\Sigma$. Ako je $\N\varphi$ parcijalno rekurzivna, tada je po teoremu~\ref{tm:pir} RAM-izračunljiva. Tada je po teoremu~\ref{tm:krit} (primijenjenom na kodiranje $\N\Sigma$) $\varphi$ Turing-izračunljiva, a onda je po teoremu~\ref{tm:tikp} (primijenjenom na kodiranje $\N'\Sigma$) $\N'\varphi$ parcijalno rekurzivna. Zamjenom $\N\Sigma$ i $\N'\Sigma$ se dokaže i drugi smjer, dakle $\N\varphi$ je parcijalno rekurzivna ako i samo ako je $\N'\varphi$ parcijalno rekurzivna.
\end{proof}

\input{tbroj.tex}