Primitiivirekursiiviset funktiot

Yleistä

1900-luvun alkupuoli oli matemaattisen logiikan kulta-aikaa, jolloin suuret matemaatikot, kuten Alan Turing (1912-1954), Kurt Gödel (1906-1978), Alonzo Church (1903-1995), Emil Post (1897-1954) ja useat muut kehittivät useita matemaattisia malleja, jotka mallinsivat nykyaikaisia tietokoneita ennen kuin niitä oli varsinaisesti rakennettu. Samalla pystyttiin jo ennen tietokoneiden keksimistä päättelemään, mitä on tietokoneella laskettavissa ja mitä ei, vaikka resursseja olisi kuinka paljon. Alan Turing tunnettiin erityisesti Turingin koneesta, joka vastaa tietokonetta, jolla on nauhamainen muisti, rekistereitä ja lukupää. Emil Post vastaavasti oli merkkijonojärjestelmien uranuurtaja, Alonzo Church kehitti sittemmin $\lambda$-laskentana tunnetun järjestelmän, joka simuloi sitä, kuinka tietokoneohjelmien funktiot ottavat parametreja ja käsittelevät niitä. Church teki erityisen tunnetuksi konseptin, jossa funktiot voivat ottaa parametreikseen toisia funktioita, mikä nykyään tunnetaan funktionaalisena ohjelmointina, ollen käytössä useissa nykyaikaisissa Javascript-kirjastoissa, kuten React.JS:ssä. Kurt Gödel keksi yksinkertaisehkot määritelmät lukuteoreettisille funktioille, sekä järjestelmän, jolla lukupareja, useamman luvun listoja tai merkkijonoja voidaan koodata luonnollisiksi luvuiksi. Tällainen systeemi on nykyään käytössä esimerkiksi UTF-8-merkistökoodauksessa. Tämä artikkeli käsittelee lukuteoreettisten funktioiden merkittävää osajoukkoa, primitiivirekursiivisia funktioita.

Primitiivirekursiivisten funktioiden määritelmä

Primitiivirekursiiviset funktiot ovat eräitä funktioita nollan tai useamman luonnollisen luvun listalta yhdelle luonnolliselle luvulle. Funktiot tyhjältä listalta luonnolliselle luvuille ovat luonnolliset luvut itse, kuten $0$, $1$, $2$, $3$ jne.

Primitiivirekursiiviset funktiot kattavat initiaalifunktiot, eli nollafunktion, seuraajan ja projektiofunktiot ja ovat suljettuja funktioiden yhdistämisen ja primitiivirekursion suhteen. Seuraavassa merkitään $\overrightarrow{x}$, jos tarkoitetaan $n$ kappaleen luonnollisen luvun listaa $x_0,x_1,x_2,\dots ,x_{n-1}$.

Initiaalifunktiot

Nollafunktio

$0$-paikkainen nollafunktio $\zeta$, määritellään
$$\zeta ()=0$$
Tämä vastaa p.r. funktioissa itse lukua $0$.

Seuraaja

$1$-paikkainen seuraajafunktio $\sigma$, ”määritellään” tai tulee myöhemmin tässä artikkelissa tarkoittamaan lisäämistä yhdellä, esimerkiksi:
$$\sigma (0)=1,\sigma (1)=2\dots$$
Funktion täysi merkitys voidaan esitellä vasta funktioiden yhdistämisen määritelmän jälkeen.

Projektio

$n$-paikkainen $m$-projektiofunktio ${\pi }_m^n$ poimii listasta $\overrightarrow{x}=x_0,x_1,\dots ,x_{n-1}$ alkion kohdasta $m$, jolloin indeksointi (tässä artikkelissa) alkaa nollasta. Esimerkiksi:
$${\pi }_1^3(5,3,1)=3$$
Myöhemmin vakiofunktioiden esittämisen jälkeen projektiofunktiota voidaan yksinkertaistaa poistamalla oletus sen paikkaluvusta.

Primitiivirekursiiviset operaatiot

Yhdistäminen

Jos $g$ on $m$-paikkainen funktio ja $\overrightarrow{h}=h_0,h_1\dots h_{m-1}$, $n$-paikkaisia funktioita, niin $g$:n ja $\overrightarrow{h}$:n yhdiste
$$f=g(\overrightarrow{h}(\overrightarrow{x}))$$
on primitiivirekursiivinen. Merkitään
$$f=(\gamma g\overrightarrow{h})$$
tai
$$f=(\gamma g{h}_0{h}_1\dots h_{m-1})$$
Vakiofunktioiden esittämisen jälkeen voidaan löystää oletusta siitä, että kaikki $\overrightarrow{h}$:oon kuuluvat funktiot olisivat täsmälleen $n$-paikkaisia.

Primitiivirekursio

Jos $g$ on $n$-paikkainen funktio ja $h$ on $n+2$, paikkainen funktio, niin $f$ on $n+1$-paikkainen funktio, joka saadaan $g$:stä ja $h$:sta primitiivirekursiolla:
$$\{\begin{array}{ccc}f(0,\overrightarrow{x})& =& g(\overrightarrow{x})\\ f(n+1,\overrightarrow{x})& =& h(n,f(n,\overrightarrow{x}),\overrightarrow{x})\end{array}$$
Merkitään
$$f=(\rho gh)$$
Vakiofunktioiden esittämisen jälkeen voidaan löystää oletusta $g$:n ja $h$:n paikkaluvuista.

Numeraalit ja vakiofunktiot

(Church)-numeraalit

Kun yhdistäminen on esitelty, voidaan luonnollisten lukujen määritelmät kirjoittaa sen avulla seuraavasti:
$$\begin{array}{ccc}0& =& \zeta \\ 1& =& (\gamma \sigma \zeta )\\ 2& =& (\gamma \sigma (\gamma \sigma \zeta ))\\ 3& =& \left(\gamma \sigma (\gamma \sigma (\gamma \sigma \zeta ))\right)\\ \dots \end{array}$$
Jatkossa näitä monimutkaisempia muodollisia määritelmiä vältetään ja luonnolliset luvut kirjoitetaan numeroilla.

Vakiofunktiot

Monesti tulee tilanne, jossa tarvitaan vakiofunktiota, joka kuitenkin ottaa vastaan parametreja, mutta ei käytä niitä mihinkään. Viitaten yllä primitiivirekursion määritelmään, $1$-paikkainen $0$-funktio voitaisiin saada aikaan seuraavasti:
$$\{\begin{array}{ccc}f(0)& =& 0\\ f(n+1)& =& f(n)\end{array}$$
Tämä olisi muodollisesti $f=(\rho \zeta {\pi }_1^2)$. Yleisesti voidaan kaikki funktiot $K_m^n(\overrightarrow{x})=m$, mikä tarkoittaa $n$-parametrista vakiofunktiota, jonka arvo on aina $m$, johtaa rekursiivisilla säännöillä:
$$\{\begin{array}{ccc}{K}_0^0& =& \zeta \\ K_{m+1}^n& =& (\gamma \sigma K_m^n)\\ K_m^{n+1}& =& (\rho K_m^n{\pi }_1^{n+2})\end{array}$$

Eksplisiittinen transformaatio

Koska projektiosääntö mahdollistaa myös funktion argumenttien paikan vaihtamisen, eli käytännössä, jos $f(x,y)$ on p.r., niin myös $g(x,y)=f(y,x)$ on p.r., muodollisesti $g=(f{\pi }_1^2{\pi }_0^2)$, niin voidaan päätellä, että ylimääräiset huomiotta jäävät parametrit missä tahansa kohdassa listaa eivät muuta niiden funktioiden perhettä, joita voidaan normaaleillakin p.r. funktioiden säännöillä luoda. Kun tehdään lisäoletus ”projisoinnista listan ulkopuolelle”, eli parametrit, joita ei erikseen ole määritelty, mutta joita kysytään, ovat nollia, voidaan luopua projektiofunktiossa listan pituuden esittelystä ja sallia funktioiden yhdistämiset ja primitiivirekursiot ilman tarkkaa oletusta parametrien määristä ja järjestyksestä. Jatkossa määritellään, että ${\pi }_m(\overrightarrow{x})$ on vektorin alkio kohdassa $m$ tai $0$, jos alkio on vektorin ulkopuolella. Esimerkin vuoksi saatetaan edelleen joissakin kohden käyttää tarkkaa muotoa.

Peruslaskutoimituksia

Summa

Kahden luvun summa $n+x$ on primitiivirekursiivinen. Yksinkertaistetussa muodossa voidaan ensin havaita, että:
$$\{\begin{array}{ccc}n+0& =& n\\ (n+1)+x& =& \sigma (n+x)\end{array}$$
Muodollisesti $\mathrm{plus}=\left(\rho ({\pi }_0^1(\gamma \sigma {\pi }_1^3))\right)$.

Rajoitettu edeltäjä

Rajoitettu edeltäjä, jossa minkä tahansa muun luvun paitsi luvun $0$ edeltäjä on sitä yhtä pienempi luku, on p.r.
$$\{\begin{array}{ccc}{\sigma }^{-1}(0)& =& 0\\ {\sigma }^{-1}(n+1)& =& n\end{array}$$
Muodollisesti ${\sigma }^{-1}=(\rho \zeta {\pi }_0^2)$.

Rajoitettu vähennyslasku

Rajoitettu vähennyslasku $x{-}^{\prime }n=\mathrm{monus}(n,x)$ on p.r.
$$\{\begin{array}{ccc}\mathrm{monus}(0,x)& =& x\\ \mathrm{monus}(n+1,x)& =& {\sigma }^{-1}\mathrm{monus}(n,x)\end{array}$$
Muodollisesti $\mathrm{monus}=\left(\rho ({\pi }_0^1(\gamma {\sigma }^{-1}{\pi }_1^3))\right)=\left(\rho \left({\pi }_0^1(\gamma (\rho \zeta {\pi }_0^2){\pi }_1^3)\right)\right)$. Rajoitettu vähennyslasku poikkeaa normaalista vähennyslaskusta siten, että negatiiviset luvut eivät ole käytössä, joten jos $x\le y$, niin vähennyslaskun $x{-}^{\prime }y$ tulos on aina $0$, muuten tavallinen vähennyslaskun tulos. Myöhemmin havainnollistetaan, kuinka näin voidaan toteuttaa loogisia operaatioita.

Tulo

Tulo $n\cdot x=\mathrm{prod}(n,x)$ on p.r.
$$\{\begin{array}{ccc}\mathrm{prod}(0,x)& =& 0\\ \mathrm{prod}(n+1,x)& =& \mathrm{plus}(\mathrm{prod}(n,x),x)\end{array}$$
Muodollisesti
$\mathrm{prod}=(\rho K_0^1(\gamma \mathrm{plus}{\pi }_1^3{\pi }_2^3))$. Tässä kohden on viimeistään huomattava, kuinka monimutkaista voi olla varmistaa, että primitiivirekursio-operaatiossa $\rho$ on funktioilla oikea argumenttien lukumäärä. Tarvittiin esimerkiksi $K_0^1$ pelkän $\zeta$:n sijaan.

Logiikkaa

Predikaatit

Useissa loogisissa lausekkeissa kiinnostaa lukuarvojen sijasta vain, onko lause tosi $\mathrm{\top }$ vai epätosi $\mathrm{\perp }$. Voidaan sopia, että epätotta arvoa vastaa $0$ ja totta arvoa vastaa $1$. Jos on funktio $P_f(\overrightarrow{x})$, joka voi saada vain arvot $0$ ja $1$, sanotaan, että $P_f$ on predikaatin $P$ karakteristinen funktio. Predikaatit, joiden karakteristinen funktio on p.r. ovat primitiivirekursiivisia predikaatteja. Seuraavassa taulukossa on lueteltu joitakin predikaattien operaatioita:

Lauseke	Merkitys
$P,P=\mathrm{\top }$	$P$ on tosi
$\mathrm{\neg }P,P=\mathrm{\perp }$	$P$ on epätosi
$P\wedge Q$	JA: $P$ ja $Q$ ovat molemmat tosia
$P\vee Q$	TAI: Ainakin jompikumpi $P$ tai $Q$ on tosi
$P\to Q$	$P$:stä seuraa $Q$, sama kuin $\mathrm{\neg }P\vee Q$.
$P\leftrightarrow Q$	$P$ ja $Q$ ovat samoja
$P\nleftrightarrow Q$	ERI: Joko $P$ tai $Q$, ei molempia

Kaikki taulukon operaattorit ovat primitiivirekursiivisia predikaatteja. Todistetaan tämä muutamille tärkeimmille, loppujen todistukset voi tehdä harjoitustehtävänä. $P=\mathrm{\top }$ on p.r., koska $P_f=1$, $P=\mathrm{\perp }$ on p.r., koska $P_f=0$, $R=\mathrm{\neg }P$ on p.r. koska $R_f=1{-}^{\prime }{P}_f$, $R=P\wedge Q$ on p.r. koska $R_f=P_f\cdot Q_f$, $P\vee Q=\mathrm{\neg }(\mathrm{\neg }P\wedge \mathrm{\neg }Q)$ ja $P\to Q=\mathrm{\neg }P\vee Q$ kuten taulukossakin mainittiin. Kaksi alinta jäävät lukijan itse pääteltäviksi. Myös muita tapoja todistaa näitä on olemassa.
Funktio $\mathrm{sgn}$, joka määritellään niin, että $\mathrm{sgn}(0)=0$ ja $1$ muuten ja joka siis muuntaa minkä tahansa funktion predikaatiksi, on myös p.r.
$$\{\begin{array}{ccc}\mathrm{sgn}(0)& =& 0\\ \mathrm{sgn}(n+1)& =& 1\end{array}$$
Vaihtoehtoisesti $\mathrm{sgn}(x)=1{-}^{\prime }(1{-}^{\prime }x)$ tai muodollisesti $\mathrm{sgn}=(\rho \zeta K_1^2)$.

Rajoitettu universaali kvantifikaatio

Jos $P(n,\overrightarrow{x})$ on primitiivirekursiivinen predikaatti, niin predikaatti
$$Q(m,\overrightarrow{x})=\mathrm{\forall }[n<m]P(n,\overrightarrow{x})$$
eli ”kaikilla $n<m$, pätee $P(n,\overrightarrow{x})$”, on myös primitiivirekursiivinen.
$$\{\begin{array}{ccc}Q(0,\overrightarrow{x})& =& \mathrm{\top }\\ Q(m+1,\overrightarrow{x})& =& Q(m,\overrightarrow{x})\wedge P(m+1,\overrightarrow{x})\end{array}$$
Rajoittamaton universaali kvantifikaatio $Q(\overrightarrow{x})=\mathrm{\forall }nP(n,\overrightarrow{x})$ sen sijaan ei ole primitiivirekursiivinen.

Rajoitettu eksistentiaalinen kvantifikaatio

Jos $P(n,\overrightarrow{x})$ on primitiivirekursiivinen predikaatti, niin predikaatti
$$Q(m,\overrightarrow{x})=\mathrm{\exists }[n<m]P(n,\overrightarrow{x})$$
eli ”on olemassa $n<m$, siten että pätee $P(n,\overrightarrow{x})$”, on myös primitiivirekursiivinen.
$$Q(m,\overrightarrow{x})=\mathrm{\neg }(\mathrm{\forall }[n<m]\mathrm{\neg }P(n,\overrightarrow{x}))$$
Taaskaan rajoittamaton eksistentiaalinen kvantifikaatio $Q(\overrightarrow{x})=\mathrm{\exists }nP(n,\overrightarrow{x})$ ei ole p.r.

Yhtäsuuruus ja erisuuruus

Lukujen yhtäsuuruuden tai suuruusjärjestyksen määrittäminen on p.r. Esimerkiksi sen testaaminen, onko luku $0$, voidaan määritellä
$$\{\begin{array}{ccc}\text{0?}(0)& =& \mathrm{\top }\\ \text{0?}(n+1)& =& \mathrm{\perp }\end{array}$$
Lisäksi $(x\le y)=(x{-}^{\prime }y=0)$ ja $(x=y)=((x\le y)\wedge (y\le x))$.

Lisää lukujen laskutoimituksia

Rajoitettu summa ja tulo

Jos $\varphi (n,\overrightarrow{x})$ on primitiivirekursiivinen funktio, niin myös $f(m,\overrightarrow{x})=\sum _{n=0}^{m-1}\varphi (n,\overrightarrow{x})$ on primitiivirekursiivinen.
$$\{\begin{array}{ccc}f(0,\overrightarrow{x})& =& 0\\ f(m+1,\overrightarrow{x})& =& f(m,\overrightarrow{x})+\varphi (m+1,\overrightarrow{x})\end{array}$$
Hyvin samantapaisella kaavalla voi todistaa, että myös rajoitettu tulo $f(m,\overrightarrow{x})=\prod _{n=0}^{m-1}\varphi (n,\overrightarrow{x})$ on p.r.

Potenssiin korottaminen

Potenssiin korottaminen $m^n=\underset{n}{\underbrace{m\cdot m\cdots m}}$ on primitiivirekursiivinen:
$$m^n=\prod _{k=0}^{n-1}m$$

Rajoitettu minimalisaatio

Seuraava operaatio on hyvin tärkeä. Olemme tähän mennessä jättäneet esimerkiksi osamäärän, jakojäännöksen, juurenoton ja logaritmin käsittelemättä, koska ne ovat luonteeltaan sellaisia, että niitä varten tarvitsee ratkaista epäyhtälö tai yhtälö. Toisaalta niissä tiedetään raja, jonka puitteissa voidaan tehdä etsintä. Esimerkiksi $m/n$ ei koskaan ole suurempi kuin $m$, jos $m\ge 0$ ja $n\ge 1$.

Jos $\varphi (n,\overrightarrow{x})$ on primitiivirekursiivinen funktio, niin myös $f(m,\overrightarrow{x})=\mu [n<m]\varphi (n,\overrightarrow{x})=0$, eli pienin $n<m$ siten, että $\varphi (n,\overrightarrow{x})=0$, on primitiivirekursiivinen.
$$\{\begin{array}{ccc}f(0,\overrightarrow{x})& =& 0\\ f(m+1,\overrightarrow{x})& =& \{\begin{array}{cc}m+1& \text{jos}(\varphi (m,\overrightarrow{x})\ne 0)\wedge (f(m,\overrightarrow{x})=m)\\ f(m,\overrightarrow{x})& \text{muuten}\end{array}\end{array}$$

Osamäärä

Osamäärä on p.r.
$$x/y=(\mu [n<(x+1)]\mathrm{\neg }(ny>x)){-}^{\prime }1$$
Tässä $\mathrm{\neg }$-merkkiä käytettiin, koska ylempänä määrittelimme rajoitetun minimalisaation tarkoittavan pienimmän nollakohdan hakua, mutta nyt halusimme sitävastoin, että tietty predikaatti olisi tosi (jolloin sen negaatio on$0$).

Jakojäännös

Jakojäännös on p.r.
$$x\mathrm{\%}y=x-(x/y)\cdot y$$
On muistettava, että osamäärä on tässä kokonaisluku, joka on alaspäin pyöristetty tulos reaalisesta osamäärästä.

Juurenotto

Juurenotto on p.r.
$$\sqrt[y]{x}=(\mu [n<(x+1)]\mathrm{\neg }(n^y>x)){-}^{\prime }1$$

Logaritmi

Logaritmi on p.r.
$${\log }_y(x)=(\mu [n<(x+1)]\mathrm{\neg }(y^n>x)){-}^{\prime }1$$

Alkuluvut

Predikaatti, joka tarkastaa, onko annettu luku alkuluku, on p.r.
$$\mathrm{prime}?(x)=\mathrm{\forall }[n<x](n<2)\vee (x\mathrm{\%}n\ne 0)$$
On mahdollista todistaa, että funktio, joka antaa jotakin lukua seuraavan alkuluvun ja funktio, joka generoi $n$:nnen alkuluvun ovat molemmat p.r. Tämä jätetään harjoitustehtäväksi.

Tietorakenteet, algoritmit ja Gödel-numerointi

Tähän mennessä olemme käsitelleet vain funktioita, jotka palauttavat yksittäisen luonnollisen luvun. Kuitenkin nykyaikaisessa tietotekniikassa esiintyy tarvetta palauttaa ja käsitellä paljon muunlaistakin tietoa, kuten merkkijonoja, lukupareja, lukulistoja ja objekteja. Lisäksi tarvetta on muidenkin numeroituvien lukujoukkojen kuten kokonaislukujen, rationaalilukujen tai jopa kompleksilukujen, joiden reaali- ja imaginaariosat ovat molemmat rationaalikertoimisia, käsittelyyn ja useimmat tällaisetkin operaatiot ovat p.r. Seuraavassa käsittelemme tekniikan, jolla yksittäiseen luonnolliseen lukuun voidaan koodata näennäisesti laajempi tietorakenne. Olennaista on, että tietorakenne on numeroituva. Siksi esimerkiksi koko reaalilukujen tai kompleksilukujen joukkoa tai mitään muuta ylinumeroituvaa joukkoa ei voi käsitellä pelkillä primitiivirekursiivisilla funktioilla.

Kolmioluvut ja Cantorin parifunktio

Kolmioluvut ovat lukuja, joita saadaan laskemalla peräjälkeen luonnollisia lukuja, esimerkiksi $T(0)=0,T(1)=0+1=1,T(2)=0+1+2,\cdots$. Koska kyseessä on rajoitettu aritmeettinen summa, on se edellä käsitellyn rajoitetun summan perusteella tietenkin p.r. Kuitenkin tässä yhteydessä on hyvä muistuttaa mieleen aritmeettisen summan kaavasta johdettu kolmiolukujen kaava:
$$T(n)=\frac{n(n+1)}{2}$$
Jos nyt tarkastellaan lukupareja, jotka on ensisijaisesti järjestetty lukujen summan mukaan, toissijaisesti jälkimmäisen luvun mukaan, saadaan jono $(0,0),(1,0),(0,1),(2,0),(1,1),(0,2),(3,0),\cdots$. Havaitaan, että kaikkien parien, joiden jälkimmäinen luku on $0$, positiot (nollasta lukien) ovat kolmiolukuja! Tämä johtaa seuraavaan kaavaan, jolla kaksi luonnollista lukua pakataan yhteen lukuun:
$$\mathrm{cons}(x,y)=T(x+y)+y$$
Funktiota $\mathrm{cons}$ sanotaan keksijänsä/julkaisijansa mukaan Cantorin parifunktioksi ja se on p.r. Mitkä ovat Cantorin parifunktion käänteisfunktiot, jotka purkavat lukuparin koodauksen?
Ratkaistaan toisen asteen yhtälö:
$$\begin{array}{rcl}\frac{n(n+1)}{2}& =& m\\ n^2+n-2m& =& 0\\ n& =& \frac{-1\pm \sqrt{1+8m}}{2}\end{array}$$
Koska nyt käsitellään luonnollisia lukuja, voidaan ylläoleva lauseke pyöristää alaspäin ja käyttää neliöjuuren etumerkissä pelkkää $+$-merkkiä:
$$T^{-1}(m)=\lfloor \frac{\sqrt{1+8m}{-}^{\prime }1}{2}\rfloor$$
Nyt tiedämme, että $T^{-1}$ on p.r. ja että koodatusta lukuparista $p$ saadaan eroteltua ainakin lukuparin summa laskemalla $S=T^{-1}(p)$. Voidaan päätellä
$$\begin{array}{rcl}x+y& =& S\\ y& =& p-S\\ x& =& 2S-p\end{array}$$
Tämän perusteella voidaan määrittää p.r. funktiot $\mathrm{car}$ ja $\mathrm{cdr}$, jotka purkavat lukuparin ensimmäisen tai toisen jäsenen seuraavasti:
$$\begin{array}{rcl}\mathrm{car}(\mathrm{cons}(x,y))& =& x=2S{-}^{\prime }p\\ \mathrm{cdr}(\mathrm{cons}(x,y))& =& y=p{-}^{\prime }S\end{array}$$

Linkitetyt listat

Parifunktio mahdollistaa mielivaltaisen pituisten lukujonojen eli lukulistojen laatimisen. Sovitaan, että $L=0$ vastaa tyhjää listaa ja sitä suuremmilla luvuilla $L{-}^{\prime }1$ olkoon pari, jossa vasemmalla puolella on listan nollas alkio ja oikealla puolella listan loppuosa. Lista päättyy, jos listan loppuosa on tyhjä lista eli $0$.

Listan $L$ $n$:nnen alkion lukeminen $L[n]$ on p.r.
$$\{\begin{array}{ccc}L[0]& =& \mathrm{car}(L)\\ L[n+1]& =& \mathrm{cdr}(L)[n]\end{array}$$
samoin kuin listan pituuden $\mathrm{len}(L)$ määrittäminen:
$$\{\begin{array}{ccc}\mathrm{len}(0)& =& 0\\ \mathrm{len}(L)& =& 1+\mathrm{len}(\mathrm{cdr}(L))\text{muuten}\end{array}$$
tai listan $n$:nnen alkion poisto $\mathrm{rm}(L,n)$:
$$\{\begin{array}{ccc}\mathrm{rm}(L,0)& =& \mathrm{cdr}(L)\\ \mathrm{rm}(L,n+1)& =& \mathrm{cons}(\mathrm{car}(L),\mathrm{rm}(L,n))\end{array}$$
Näiden lisäksi lähes kaikki muutkin ajateltavissa olevat tavanomaiset listaoperaatiot, kuten tietyn listan arvon etsintä, alkioiden lisääminen listojen väliin, listojen yhteenliittäminen yms. ovat p.r. Todistukset ovat samantapaisia kuin kolme aiempaa esimerkkiä.

Binaaripuut

Binaaripuu voidaan koodata siten, että sovitaan parillisten lukujen tarkoittavan yhden luvun binaaripuuta $b/2$ ja parittomien lukujen tarkoittavan binaaripuuta, jonka vasemmalla puolella on $\mathrm{car}((b{-}^{\prime }1)/2)$ ja oikealla puolella $\mathrm{cdr}((b{-}^{\prime }1)/2)$. Binaaripuun syvyys on p.r. funktio tai alkion esiintyminen binaaripuussa tai erikseen sen vasemmalla tai oikealla puolella p.r. relaatio. Alkioiden sijainti tai syvyys puussa on myös p.r.

Merkkijonot ja unionit

Halutaan mahdollistaa merkkijonot, mutta sen lisäksi myös niiden seassa mielivaltaiset luvut. Tällöin voidaan laatia lista, kuten ylempänä, mutta sopia, että listassa oleva luku $x$ tarkoittaa lukua $x/2$, jos $x$ on parillinen tai Unicode-merkkiä $(x{-}^{\prime }1)/2$ muuten.

Objektit

Halutaan mahdollistaa taulukot, joissa on avain-arvopareja niin, että kutakin merkkijonoarvoa vastaa luku tai muu objekti, esimerkiksi:

{
  "auto": 6,
  "polkupyörä: 12,
  "moottoripyörä": (18,17)
}

Tällöin voidaan keksiä ensin yksittäisten rivien vasempia puolia vastaava koodaustapa ja sen jälkeen luoda lista pareista $\mathrm{cons}(\mathrm{VP},\mathrm{OP})$.

Johtopäätös

Olemme havainneet, että lähes kaikki ajateltavissa olevat lukujen ja muiden rakenteiden operaatiot, joita esiintyy, ovat primitiivirekursiivisia. Artikkelisarjan jälkimmäisessä osassa käydään läpi funktioita, jotka ovat kyllä laskettavia, mutta eivät ole primitiivirekursiivisia. Lisäksi osoitamme, että tietyt funktiot ja relaatiot eivät ole laskettavia. Tätä yllättävää tulosta ja sen eri variaatioita kutsutaan Gödelin lukuteorian epätäydellisyyslauseeksi.

Artikkelisarjan seuraava osa on täällä.