1900-luvun alkupuoli oli matemaattisen logiikan kulta-aikaa, jolloin suuret matemaatikot, kuten Alan Turing (1912-1954), Kurt G\u00f6del (1906-1978), Alonzo Church (1903-1995), Emil Post (1897-1954) ja useat muut kehittiv\u00e4t useita matemaattisia malleja, jotka mallinsivat nykyaikaisia tietokoneita ennen kuin niit\u00e4 oli varsinaisesti rakennettu. Samalla pystyttiin jo ennen tietokoneiden keksimist\u00e4 p\u00e4\u00e4ttelem\u00e4\u00e4n, mit\u00e4 on tietokoneella laskettavissa ja mit\u00e4 ei, vaikka resursseja olisi kuinka paljon. Alan Turing tunnettiin erityisesti Turingin koneesta, joka vastaa tietokonetta, jolla on nauhamainen muisti, rekistereit\u00e4 ja lukup\u00e4\u00e4. Emil Post vastaavasti oli merkkijonoj\u00e4rjestelmien uranuurtaja, Alonzo Church kehitti sittemmin $\\lambda$-laskentana tunnetun j\u00e4rjestelm\u00e4n, joka simuloi sit\u00e4, kuinka tietokoneohjelmien funktiot ottavat parametreja ja k\u00e4sittelev\u00e4t niit\u00e4. Church teki erityisen tunnetuksi konseptin, jossa funktiot voivat ottaa parametreikseen toisia funktioita, mik\u00e4 nyky\u00e4\u00e4n tunnetaan funktionaalisena ohjelmointina, ollen k\u00e4yt\u00f6ss\u00e4 useissa nykyaikaisissa Javascript-kirjastoissa, kuten React.JS:ss\u00e4. Kurt G\u00f6del keksi yksinkertaisehkot m\u00e4\u00e4ritelm\u00e4t lukuteoreettisille funktioille, sek\u00e4 j\u00e4rjestelm\u00e4n, jolla lukupareja, useamman luvun listoja tai merkkijonoja voidaan koodata luonnollisiksi luvuiksi. T\u00e4llainen systeemi on nyky\u00e4\u00e4n k\u00e4yt\u00f6ss\u00e4 esimerkiksi UTF-8-merkist\u00f6koodauksessa. T\u00e4m\u00e4 artikkeli k\u00e4sittelee lukuteoreettisten funktioiden merkitt\u00e4v\u00e4\u00e4 osajoukkoa, primitiivirekursiivisia funktioita.<\/p>\n\n\n\n
Primitiivirekursiiviset funktiot ovat er\u00e4it\u00e4 funktioita nollan tai useamman luonnollisen luvun listalta yhdelle luonnolliselle luvulle. Funktiot tyhj\u00e4lt\u00e4 listalta luonnolliselle luvuille ovat luonnolliset luvut itse, kuten $0$, $1$, $2$, $3$ jne.<\/p>\n\n\n\n
Primitiivirekursiiviset funktiot kattavat initiaalifunktiot, eli nollafunktion, seuraajan ja projektiofunktiot ja ovat suljettuja funktioiden yhdist\u00e4misen ja primitiivirekursion suhteen. Seuraavassa merkit\u00e4\u00e4n $\\vec{x}$, jos tarkoitetaan $n$ kappaleen luonnollisen luvun listaa $x_0,x_1,x_2, … ,x_{n-1}$.<\/p>\n\n\n\n
$0$-paikkainen nollafunktio $\\zeta$, m\u00e4\u00e4ritell\u00e4\u00e4n
$$\\zeta()=0$$
T\u00e4m\u00e4 vastaa p.r. funktioissa itse lukua $0$.<\/p>\n\n\n\n
$1$-paikkainen seuraajafunktio $\\sigma$, ”m\u00e4\u00e4ritell\u00e4\u00e4n” tai tulee my\u00f6hemmin t\u00e4ss\u00e4 artikkelissa tarkoittamaan lis\u00e4\u00e4mist\u00e4 yhdell\u00e4, esimerkiksi:
$$\\sigma(0)=1, \\sigma(1)=2 …$$
Funktion t\u00e4ysi merkitys voidaan esitell\u00e4 vasta funktioiden yhdist\u00e4misen m\u00e4\u00e4ritelm\u00e4n j\u00e4lkeen.<\/p>\n\n\n\n
$n$-paikkainen $m$-projektiofunktio $\\pi_m^n$ poimii listasta $\\vec{x}=x_0,x_1,…,x_{n-1}$ alkion kohdasta $m$, jolloin indeksointi (t\u00e4ss\u00e4 artikkelissa) alkaa nollasta. Esimerkiksi:
$$\\pi_1^3(5,3,1)=3$$
My\u00f6hemmin vakiofunktioiden esitt\u00e4misen j\u00e4lkeen projektiofunktiota voidaan yksinkertaistaa poistamalla oletus sen paikkaluvusta.<\/p>\n\n\n\n
Jos $g$ on $m$-paikkainen funktio ja $\\vec{h}=h_0,h_1…h_{m-1}$, $n$-paikkaisia funktioita, niin $g$:n ja $\\vec{h}$:n yhdiste
$$f=g(\\vec{h}(\\vec{x}))$$
on primitiivirekursiivinen. Merkit\u00e4\u00e4n
$$f=(\\gamma g\\vec{h})$$
tai
$$f=(\\gamma g h_0 h_1 … h_{m-1})$$
Vakiofunktioiden esitt\u00e4misen j\u00e4lkeen voidaan l\u00f6yst\u00e4\u00e4 oletusta siit\u00e4, ett\u00e4 kaikki $\\vec{h}$:oon kuuluvat funktiot olisivat t\u00e4sm\u00e4lleen $n$-paikkaisia.<\/p>\n\n\n\n
Jos $g$ on $n$-paikkainen funktio ja $h$ on $n+2$, paikkainen funktio, niin $f$ on $n+1$-paikkainen funktio, joka saadaan $g$:st\u00e4 ja $h$:sta primitiivirekursiolla:
$$\\left\\{
\\begin{array}{ccc}
f(0,\\vec{x}) & = & g(\\vec{x}) \\\\
f(n+1,\\vec{x}) & = & h\\left(n,f(n,\\vec{x}),\\vec{x}\\right)
\\end{array}
\\right.$$
Merkit\u00e4\u00e4n
$$f=(\\rho g h)$$
Vakiofunktioiden esitt\u00e4misen j\u00e4lkeen voidaan l\u00f6yst\u00e4\u00e4 oletusta $g$:n ja $h$:n paikkaluvuista.<\/p>\n\n\n\n
Kun yhdist\u00e4minen on esitelty, voidaan luonnollisten lukujen m\u00e4\u00e4ritelm\u00e4t kirjoittaa sen avulla seuraavasti:
\\begin{array}{ccc}
0 & = & \\zeta \\\\
1 & = & (\\gamma \\sigma \\zeta) \\\\
2 & = & \\left(\\gamma \\sigma (\\gamma \\sigma \\zeta)\\right) \\\\
3 & = & \\left(\\gamma \\sigma \\left(\\gamma \\sigma (\\gamma \\sigma \\zeta)\\right)\\right) \\\\
…
\\end{array}
Jatkossa n\u00e4it\u00e4 monimutkaisempia muodollisia m\u00e4\u00e4ritelmi\u00e4 v\u00e4ltet\u00e4\u00e4n ja luonnolliset luvut kirjoitetaan numeroilla.<\/p>\n\n\n\n
Monesti tulee tilanne, jossa tarvitaan vakiofunktiota, joka kuitenkin ottaa vastaan parametreja, mutta ei k\u00e4yt\u00e4 niit\u00e4 mihink\u00e4\u00e4n. Viitaten yll\u00e4 primitiivirekursion m\u00e4\u00e4ritelm\u00e4\u00e4n, $1$-paikkainen $0$-funktio voitaisiin saada aikaan seuraavasti:
$$\\left\\{
\\begin{array}{ccc}
f(0) & = & 0 \\\\
f(n+1) & = & f(n)
\\end{array}
\\right.$$
T\u00e4m\u00e4 olisi muodollisesti $f=(\\rho\\zeta\\pi_1^2)$. Yleisesti voidaan kaikki funktiot $K_m^n(\\vec{x})=m$, mik\u00e4 tarkoittaa $n$-parametrista vakiofunktiota, jonka arvo on aina $m$, johtaa rekursiivisilla s\u00e4\u00e4nn\u00f6ill\u00e4:
$$\\left\\{
\\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}
\\right.$$<\/p>\n\n\n\n
Koska projektios\u00e4\u00e4nt\u00f6 mahdollistaa my\u00f6s funktion argumenttien paikan vaihtamisen, eli k\u00e4yt\u00e4nn\u00f6ss\u00e4, jos $f(x,y)$ on p.r., niin my\u00f6s $g(x,y)=f(y,x)$ on p.r., muodollisesti $g=(f\\pi_1^2 \\pi_0^2)$, niin voidaan p\u00e4\u00e4tell\u00e4, ett\u00e4 ylim\u00e4\u00e4r\u00e4iset huomiotta j\u00e4\u00e4v\u00e4t parametrit miss\u00e4 tahansa kohdassa listaa eiv\u00e4t muuta niiden funktioiden perhett\u00e4, joita voidaan normaaleillakin p.r. funktioiden s\u00e4\u00e4nn\u00f6ill\u00e4 luoda. Kun tehd\u00e4\u00e4n lis\u00e4oletus ”projisoinnista listan ulkopuolelle”, eli parametrit, joita ei erikseen ole m\u00e4\u00e4ritelty, mutta joita kysyt\u00e4\u00e4n, ovat nollia, voidaan luopua projektiofunktiossa listan pituuden esittelyst\u00e4 ja sallia funktioiden yhdist\u00e4miset ja primitiivirekursiot ilman tarkkaa oletusta parametrien m\u00e4\u00e4rist\u00e4 ja j\u00e4rjestyksest\u00e4. Jatkossa m\u00e4\u00e4ritell\u00e4\u00e4n, ett\u00e4 $\\pi_m(\\vec{x})$ on vektorin alkio kohdassa $m$ tai $0$, jos alkio on vektorin ulkopuolella. Esimerkin vuoksi saatetaan edelleen joissakin kohden k\u00e4ytt\u00e4\u00e4 tarkkaa muotoa.<\/p>\n\n\n\n
Kahden luvun summa $n+x$ on primitiivirekursiivinen. Yksinkertaistetussa muodossa voidaan ensin havaita, ett\u00e4:
$$\\left\\{
\\begin{array}{ccc}
n+0 & = & n \\\\
(n+1)+x & = & \\sigma(n+x)
\\end{array}
\\right.$$
Muodollisesti $\\mathrm{plus}=\\left(\\rho\\left(\\pi_0^1(\\gamma\\sigma\\pi_1^3)\\right)\\right)$.<\/p>\n\n\n\n
Rajoitettu edelt\u00e4j\u00e4, jossa mink\u00e4 tahansa muun luvun paitsi luvun $0$ edelt\u00e4j\u00e4 on sit\u00e4 yht\u00e4 pienempi luku, on p.r.
$$\\left\\{
\\begin{array}{ccc}
\\sigma^{-1}(0) & = & 0 \\\\
\\sigma^{-1}(n+1) & = & n
\\end{array}
\\right.$$
Muodollisesti $\\sigma^{-1}=(\\rho\\zeta\\pi_0^2)$.<\/p>\n\n\n\n
Rajoitettu v\u00e4hennyslasku $x-’n=\\mathrm{monus}(n,x)$ on p.r.
$$\\left\\{
\\begin{array}{ccc}
\\mathrm{monus}(0,x) & = & x \\\\
\\mathrm{monus}(n+1,x) & = & \\sigma^{-1}\\mathrm{monus}(n,x)
\\end{array}
\\right.$$
Muodollisesti $\\mathrm{monus}=\\left(\\rho\\left(\\pi_0^1(\\gamma\\sigma^{-1}\\pi_1^3)\\right)\\right)=\\left(\\rho\\left(\\pi_0^1\\left(\\gamma(\\rho\\zeta\\pi_0^2)\\pi_1^3\\right)\\right)\\right)$. Rajoitettu v\u00e4hennyslasku poikkeaa normaalista v\u00e4hennyslaskusta siten, ett\u00e4 negatiiviset luvut eiv\u00e4t ole k\u00e4yt\u00f6ss\u00e4, joten jos $x\\le y$, niin v\u00e4hennyslaskun $x-’y$ tulos on aina $0$, muuten tavallinen v\u00e4hennyslaskun tulos. My\u00f6hemmin havainnollistetaan, kuinka n\u00e4in voidaan toteuttaa loogisia operaatioita.<\/p>\n\n\n\n
Tulo $n\\cdot x=\\mathrm{prod}(n,x)$ on p.r.
$$\\left\\{
\\begin{array}{ccc}
\\mathrm{prod}(0,x) & = & 0 \\\\
\\mathrm{prod}(n+1,x) & = & \\mathrm{plus}(\\mathrm{prod}(n,x),x)
\\end{array}
\\right.$$
Muodollisesti
$\\mathrm{prod}=(\\rho K_0^1(\\gamma\\ \\mathrm{plus}\\ \\pi_1^3 \\pi_2^3))$. T\u00e4ss\u00e4 kohden on viimeist\u00e4\u00e4n huomattava, kuinka monimutkaista voi olla varmistaa, ett\u00e4 primitiivirekursio-operaatiossa $\\rho$ on funktioilla oikea argumenttien lukum\u00e4\u00e4r\u00e4. Tarvittiin esimerkiksi $K_0^1$ pelk\u00e4n $\\zeta$:n sijaan.<\/p>\n\n\n\n
Useissa loogisissa lausekkeissa kiinnostaa lukuarvojen sijasta vain, onko lause tosi $\\top$ vai ep\u00e4tosi $\\bot$. Voidaan sopia, ett\u00e4 ep\u00e4totta arvoa vastaa $0$ ja totta arvoa vastaa $1$. Jos on funktio $P_f(\\vec{x})$, joka voi saada vain arvot $0$ ja $1$, sanotaan, ett\u00e4 $P_f$ on predikaatin $P$ karakteristinen funktio. Predikaatit, joiden karakteristinen funktio on p.r. ovat primitiivirekursiivisia predikaatteja. Seuraavassa taulukossa on lueteltu joitakin predikaattien operaatioita:<\/p>\n\n\n\n Kaikki taulukon operaattorit ovat primitiivirekursiivisia predikaatteja. Todistetaan t\u00e4m\u00e4 muutamille t\u00e4rkeimmille, loppujen todistukset voi tehd\u00e4 harjoitusteht\u00e4v\u00e4n\u00e4. $P=\\top$ on p.r., koska $P_f=1$, $P=\\bot$ on p.r., koska $P_f=0$, $R=\\lnot P$ on p.r. koska $R_f=1-’P_f$, $R=P\\land Q$ on p.r. koska $R_f=P_f\\cdot Q_f$, $P\\lor Q=\\lnot(\\lnot P \\land \\lnot Q)$ ja $P\\to Q=\\lnot P\\lor Q$ kuten taulukossakin mainittiin. Kaksi alinta j\u00e4\u00e4v\u00e4t lukijan itse p\u00e4\u00e4telt\u00e4viksi. My\u00f6s muita tapoja todistaa n\u00e4it\u00e4 on olemassa. Jos $P(n,\\vec{x})$ on primitiivirekursiivinen predikaatti, niin predikaatti Jos $P(n,\\vec{x})$ on primitiivirekursiivinen predikaatti, niin predikaatti Lukujen yht\u00e4suuruuden tai suuruusj\u00e4rjestyksen m\u00e4\u00e4ritt\u00e4minen on p.r. Esimerkiksi sen testaaminen, onko luku $0$, voidaan m\u00e4\u00e4ritell\u00e4 Jos $\\phi(n,\\vec{x})$ on primitiivirekursiivinen funktio, niin my\u00f6s $f(m,\\vec{x})=\\sum_{n=0}^{m-1} \\phi(n,\\vec{x})$ on primitiivirekursiivinen. Potenssiin korottaminen $m^n=\\underbrace{m\\cdot m\\cdots m}_n$ on primitiivirekursiivinen: Seuraava operaatio on hyvin t\u00e4rke\u00e4. Olemme t\u00e4h\u00e4n menness\u00e4 j\u00e4tt\u00e4neet esimerkiksi osam\u00e4\u00e4r\u00e4n, jakoj\u00e4\u00e4nn\u00f6ksen, juurenoton ja logaritmin k\u00e4sittelem\u00e4tt\u00e4, koska ne ovat luonteeltaan sellaisia, ett\u00e4 niit\u00e4 varten tarvitsee ratkaista ep\u00e4yht\u00e4l\u00f6 tai yht\u00e4l\u00f6. Toisaalta niiss\u00e4 tiedet\u00e4\u00e4n raja, jonka puitteissa voidaan tehd\u00e4 etsint\u00e4. Esimerkiksi $m\/n$ ei koskaan ole suurempi kuin $m$, jos $m\\ge 0$ ja $n\\ge 1$.<\/p>\n\n\n\n Jos $\\phi(n,\\vec{x})$ on primitiivirekursiivinen funktio, niin my\u00f6s $f(m,\\vec{x})=\\mu[n<m]\\phi(n,\\vec{x})=0$, eli pienin $n<m$ siten, ett\u00e4 $\\phi(n,\\vec{x})=0$, on primitiivirekursiivinen. Osam\u00e4\u00e4r\u00e4 on p.r. Jakoj\u00e4\u00e4nn\u00f6s on p.r. Juurenotto on p.r. Logaritmi on p.r. Predikaatti, joka tarkastaa, onko annettu luku alkuluku, on p.r. T\u00e4h\u00e4n menness\u00e4 olemme k\u00e4sitelleet vain funktioita, jotka palauttavat yksitt\u00e4isen luonnollisen luvun. Kuitenkin nykyaikaisessa tietotekniikassa esiintyy tarvetta palauttaa ja k\u00e4sitell\u00e4 paljon muunlaistakin tietoa, kuten merkkijonoja, lukupareja, lukulistoja ja objekteja. Lis\u00e4ksi tarvetta on muidenkin numeroituvien lukujoukkojen kuten kokonaislukujen, rationaalilukujen tai jopa kompleksilukujen, joiden reaali- ja imaginaariosat ovat molemmat rationaalikertoimisia, k\u00e4sittelyyn ja useimmat t\u00e4llaisetkin operaatiot ovat p.r. Seuraavassa k\u00e4sittelemme tekniikan, jolla yksitt\u00e4iseen luonnolliseen lukuun voidaan koodata n\u00e4enn\u00e4isesti laajempi tietorakenne. Olennaista on, ett\u00e4 tietorakenne on numeroituva. Siksi esimerkiksi koko reaalilukujen tai kompleksilukujen joukkoa tai mit\u00e4\u00e4n muuta ylinumeroituvaa joukkoa ei voi k\u00e4sitell\u00e4 pelkill\u00e4 primitiivirekursiivisilla funktioilla.<\/p>\n\n\n\n Kolmioluvut ovat lukuja, joita saadaan laskemalla per\u00e4j\u00e4lkeen luonnollisia lukuja, esimerkiksi $T(0)=0, T(1)=0+1=1, T(2)=0+1+2,\\cdots$. Koska kyseess\u00e4 on rajoitettu aritmeettinen summa, on se edell\u00e4 k\u00e4sitellyn rajoitetun summan perusteella tietenkin p.r. Kuitenkin t\u00e4ss\u00e4 yhteydess\u00e4 on hyv\u00e4 muistuttaa mieleen aritmeettisen summan kaavasta johdettu kolmiolukujen kaava: Parifunktio mahdollistaa mielivaltaisen pituisten lukujonojen eli lukulistojen laatimisen. Sovitaan, ett\u00e4 $L=0$ vastaa tyhj\u00e4\u00e4 listaa ja sit\u00e4 suuremmilla luvuilla $L-’1$ olkoon pari, jossa vasemmalla puolella on listan nollas alkio ja oikealla puolella listan loppuosa. Lista p\u00e4\u00e4ttyy, jos listan loppuosa on tyhj\u00e4 lista eli $0$.<\/p>\n\n\n\n Listan $L$ $n$:nnen alkion lukeminen $L[n]$ on p.r. Binaaripuu voidaan koodata siten, ett\u00e4 sovitaan parillisten lukujen tarkoittavan yhden luvun binaaripuuta $b\/2$ ja parittomien lukujen tarkoittavan binaaripuuta, jonka vasemmalla puolella on $\\mathrm{car}((b-’1)\/2)$ ja oikealla puolella $\\mathrm{cdr}((b-’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\u00f6s p.r.<\/p>\n\n\n\n Halutaan mahdollistaa merkkijonot, mutta sen lis\u00e4ksi my\u00f6s niiden seassa mielivaltaiset luvut. T\u00e4ll\u00f6in voidaan laatia lista, kuten ylemp\u00e4n\u00e4, mutta sopia, ett\u00e4 listassa oleva luku $x$ tarkoittaa lukua $x\/2$, jos $x$ on parillinen tai Unicode-merkki\u00e4 $(x-’1)\/2$ muuten.<\/p>\n\n\n\n Halutaan mahdollistaa taulukot, joissa on avain-arvopareja niin, ett\u00e4 kutakin merkkijonoarvoa vastaa luku tai muu objekti, esimerkiksi:<\/p>\n\n\n\n T\u00e4ll\u00f6in voidaan keksi\u00e4 ensin yksitt\u00e4isten rivien vasempia puolia vastaava koodaustapa ja sen j\u00e4lkeen luoda lista pareista $\\mathrm{cons}(\\mathrm{VP},\\mathrm{OP})$.<\/p>\n\n\n\n Olemme havainneet, ett\u00e4 l\u00e4hes kaikki ajateltavissa olevat lukujen ja muiden rakenteiden operaatiot, joita esiintyy, ovat primitiivirekursiivisia. Artikkelisarjan j\u00e4lkimm\u00e4isess\u00e4 osassa k\u00e4yd\u00e4\u00e4n l\u00e4pi funktioita, jotka ovat kyll\u00e4 laskettavia, mutta eiv\u00e4t ole primitiivirekursiivisia. Lis\u00e4ksi osoitamme, ett\u00e4 tietyt funktiot ja relaatiot eiv\u00e4t ole laskettavia. T\u00e4t\u00e4 yll\u00e4tt\u00e4v\u00e4\u00e4 tulosta ja sen eri variaatioita kutsutaan G\u00f6delin lukuteorian ep\u00e4t\u00e4ydellisyyslauseeksi.<\/p>\n\n\n\nLauseke<\/strong><\/td> Merkitys<\/strong><\/td><\/tr> $P,\\ P=\\top$<\/td> $P$ on tosi<\/td><\/tr> $\\lnot P,\\ P=\\bot$<\/td> $P$ on ep\u00e4tosi<\/td><\/tr> $P\\land Q$<\/td> JA: $P$ ja $Q$ ovat molemmat tosia<\/td><\/tr> $P\\lor Q$<\/td> TAI: Ainakin jompikumpi $P$ tai $Q$ on tosi<\/td><\/tr> $P\\to Q$<\/td> $P$:st\u00e4 seuraa $Q$, sama kuin $\\lnot P\\lor Q$.<\/td><\/tr> $P\\leftrightarrow Q$<\/td> $P$ ja $Q$ ovat samoja<\/td><\/tr> $P\\not\\leftrightarrow Q$<\/td> ERI: Joko $P$ tai $Q$, ei molempia<\/td><\/tr><\/tbody><\/table>
Funktio $\\mathrm{sgn}$, joka m\u00e4\u00e4ritell\u00e4\u00e4n niin, ett\u00e4 $\\mathrm{sgn}(0)=0$ ja $1$ muuten ja joka siis muuntaa mink\u00e4 tahansa funktion predikaatiksi, on my\u00f6s p.r.
$$
\\left\\{
\\begin{array}{ccc}
\\mathrm{sgn}(0) & = & 0 \\\\
\\mathrm{sgn}(n+1) & = & 1
\\end{array}
\\right.
$$
Vaihtoehtoisesti $\\mathrm{sgn}(x)=1-’(1-’x)$ tai muodollisesti $\\mathrm{sgn}=(\\rho\\zeta K_1^2)$.<\/p>\n\n\n\nRajoitettu universaali kvantifikaatio<\/h3>\n\n\n\n
$$Q(m,\\vec{x})=\\forall[n<m] P(n,\\vec{x})$$
eli ”kaikilla $n<m$, p\u00e4tee $P(n,\\vec{x})$”, on my\u00f6s primitiivirekursiivinen.
$$
\\left\\{
\\begin{array}{ccc}
Q(0,\\vec{x}) & = & \\top \\\\
Q(m+1,\\vec{x}) & = & Q(m,\\vec{x}) \\land P(m+1,\\vec{x}
)\\end{array}
\\right.
$$
Rajoittamaton universaali kvantifikaatio $Q(\\vec{x})=\\forall n P(n,\\vec{x})$ sen sijaan ei ole<\/em> primitiivirekursiivinen.<\/p>\n\n\n\nRajoitettu eksistentiaalinen kvantifikaatio<\/h3>\n\n\n\n
$$Q(m,\\vec{x})=\\exists[n<m] P(n,\\vec{x})$$
eli ”on olemassa $n<m$, siten ett\u00e4 p\u00e4tee $P(n,\\vec{x})$”, on my\u00f6s primitiivirekursiivinen.
$$
Q(m,\\vec{x})=\\lnot\\left(\\forall[n<m] \\lnot P(n,\\vec{x})\\right)
$$
Taaskaan rajoittamaton eksistentiaalinen kvantifikaatio $Q(\\vec{x})=\\exists n P(n,\\vec{x})$ ei ole p.r.<\/p>\n\n\n\nYht\u00e4suuruus ja erisuuruus<\/h3>\n\n\n\n
$$
\\left\\{
\\begin{array}{ccc}
\\textrm{0?}(0) & = & \\top \\\\
\\textrm{0?}(n+1) & = & \\bot
\\end{array}
\\right.
$$
Lis\u00e4ksi $(x\\leq y)=(x-’y=0)$ ja $(x=y)=((x\\leq y)\\land(y\\leq x))$.<\/p>\n\n\n\nLis\u00e4\u00e4 lukujen laskutoimituksia<\/h2>\n\n\n\n
Rajoitettu summa ja tulo<\/h3>\n\n\n\n
$$
\\left\\{
\\begin{array}{ccc}
f(0,\\vec{x}) & = & 0 \\\\
f(m+1,\\vec{x}) & = & f(m,\\vec{x})+\\phi(m+1,\\vec{x}
)\\end{array}
\\right.
$$
Hyvin samantapaisella kaavalla voi todistaa, ett\u00e4 my\u00f6s rajoitettu tulo $f(m,\\vec{x})=\\prod_{n=0}^{m-1} \\phi(n,\\vec{x})$ on p.r.<\/p>\n\n\n\nPotenssiin korottaminen<\/h3>\n\n\n\n
$$m^n=\\prod_{k=0}^{n-1} m$$<\/p>\n\n\n\nRajoitettu minimalisaatio<\/h3>\n\n\n\n
$$
\\left\\{
\\begin{array}{ccc}
f(0,\\vec{x}) & = & 0 \\\\
f(m+1,\\vec{x}) & = &
\\left\\{
\\begin{array}{cc}
m+1 & \\textrm{jos}\\ \\left(\\phi(m,\\vec{x})\\neq 0\\right) \\land \\left(f(m,\\vec{x})=m\\right) \\\\
f(m,\\vec{x}) & \\textrm{muuten}
\\end{array}
\\right.
\\end{array}
\\right.
$$<\/p>\n\n\n\nOsam\u00e4\u00e4r\u00e4<\/h3>\n\n\n\n
$$x\/y=\\left(\\mu[n<(x+1)]\\ \\lnot(ny>x)\\right)-’1$$
T\u00e4ss\u00e4 $\\lnot$-merkki\u00e4 k\u00e4ytettiin, koska ylemp\u00e4n\u00e4 m\u00e4\u00e4rittelimme rajoitetun minimalisaation tarkoittavan pienimm\u00e4n nollakohdan hakua, mutta nyt halusimme sit\u00e4vastoin, ett\u00e4 tietty predikaatti olisi tosi (jolloin sen negaatio on$0$).<\/p>\n\n\n\nJakoj\u00e4\u00e4nn\u00f6s<\/h3>\n\n\n\n
$$x\\%y=x-(x\/y)\\cdot y$$
On muistettava, ett\u00e4 osam\u00e4\u00e4r\u00e4 on t\u00e4ss\u00e4 kokonaisluku, joka on alasp\u00e4in py\u00f6ristetty tulos reaalisesta osam\u00e4\u00e4r\u00e4st\u00e4.<\/p>\n\n\n\nJuurenotto<\/h3>\n\n\n\n
$$\\sqrt[y]{x}=\\left(\\mu[n<(x+1)]\\ \\lnot(n^y>x)\\right)-’1$$<\/p>\n\n\n\nLogaritmi<\/h3>\n\n\n\n
$$\\log_y(x)=\\left(\\mu[n<(x+1)]\\ \\lnot(y^n>x)\\right)-’1$$<\/p>\n\n\n\nAlkuluvut<\/h3>\n\n\n\n
$$\\mathrm{prime?}(x)=\\forall[n<x]\\ (n<2)\\lor (x\\%n \\neq 0)$$
On mahdollista todistaa, ett\u00e4 funktio, joka antaa jotakin lukua seuraavan alkuluvun ja funktio, joka generoi $n$:nnen alkuluvun ovat molemmat p.r. T\u00e4m\u00e4 j\u00e4tet\u00e4\u00e4n harjoitusteht\u00e4v\u00e4ksi.<\/p>\n\n\n\nTietorakenteet, algoritmit ja G\u00f6del-numerointi<\/h2>\n\n\n\n
Kolmioluvut ja Cantorin parifunktio<\/h3>\n\n\n\n
$$
T(n)=\\frac{n(n+1)}{2}
$$
Jos nyt tarkastellaan lukupareja, jotka on ensisijaisesti j\u00e4rjestetty lukujen summan mukaan, toissijaisesti j\u00e4lkimm\u00e4isen luvun mukaan, saadaan jono $(0,0),(1,0),(0,1),(2,0),(1,1),(0,2),(3,0),\\cdots$. Havaitaan, ett\u00e4 kaikkien parien, joiden j\u00e4lkimm\u00e4inen luku on $0$, positiot (nollasta lukien) ovat kolmiolukuja! T\u00e4m\u00e4 johtaa seuraavaan kaavaan, jolla kaksi luonnollista lukua pakataan yhteen lukuun:
$$
\\mathrm{cons}(x,y)=T(x+y)+y
$$
Funktiota $\\mathrm{cons}$ sanotaan keksij\u00e4ns\u00e4\/julkaisijansa mukaan Cantorin parifunktioksi ja se on p.r. Mitk\u00e4 ovat Cantorin parifunktion k\u00e4\u00e4nteisfunktiot, jotka purkavat lukuparin koodauksen?
Ratkaistaan toisen asteen yht\u00e4l\u00f6:
$$
\\begin{eqnarray}
\\frac{n(n+1)}{2} & = & m \\\\
n^2+n-2m & = & 0 \\\\
n & = & \\frac{-1\\pm\\sqrt{1+8m}}{2}
\\end{eqnarray}
$$
Koska nyt k\u00e4sitell\u00e4\u00e4n luonnollisia lukuja, voidaan yll\u00e4oleva lauseke py\u00f6rist\u00e4\u00e4 alasp\u00e4in ja k\u00e4ytt\u00e4\u00e4 neli\u00f6juuren etumerkiss\u00e4 pelkk\u00e4\u00e4 $+$-merkki\u00e4:
$$
T^{-1}(m)=\\left\\lfloor\\frac{\\sqrt{1+8m}-’1}{2}\\right\\rfloor
$$
Nyt tied\u00e4mme, ett\u00e4 $T^{-1}$ on p.r. ja ett\u00e4 koodatusta lukuparista $p$ saadaan eroteltua ainakin lukuparin summa laskemalla $S=T^{-1}(p)$. Voidaan p\u00e4\u00e4tell\u00e4
$$
\\begin{eqnarray}
x+y & = & S \\\\
y & = & p-S \\\\
x & = & 2S-p
\\end{eqnarray}
$$
T\u00e4m\u00e4n perusteella voidaan m\u00e4\u00e4ritt\u00e4\u00e4 p.r. funktiot $\\mathrm{car}$ ja $\\mathrm{cdr}$, jotka purkavat lukuparin ensimm\u00e4isen tai toisen j\u00e4senen seuraavasti:
$$
\\begin{eqnarray}
\\mathrm{car}(\\mathrm{cons}(x,y)) & = & x=2S-’p \\\\
\\mathrm{cdr}(\\mathrm{cons}(x,y)) & = & y=p-’S
\\end{eqnarray}
$$<\/p>\n\n\n\nLinkitetyt listat<\/h3>\n\n\n\n
$$
\\left\\{
\\begin{array}{ccc}
L[0] & = & \\mathrm{car}(L) \\\\
L[n+1] & = & \\mathrm{cdr}(L)[n]
\\end{array}
\\right.
$$
samoin kuin listan pituuden $\\mathrm{len}(L)$ m\u00e4\u00e4ritt\u00e4minen:
$$
\\left\\{
\\begin{array}{ccc}
\\mathrm{len}(0) & = & 0 \\\\
\\mathrm{len}(L) & = & 1+\\mathrm{len}(\\mathrm{cdr}(L))\\quad \\textrm{muuten}
\\end{array}
\\right.
$$
tai listan $n$:nnen alkion poisto $\\mathrm{rm}(L,n)$:
$$
\\left\\{
\\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}
\\right.
$$
N\u00e4iden lis\u00e4ksi l\u00e4hes kaikki muutkin ajateltavissa olevat tavanomaiset listaoperaatiot, kuten tietyn listan arvon etsint\u00e4, alkioiden lis\u00e4\u00e4minen listojen v\u00e4liin, listojen yhteenliitt\u00e4minen yms. ovat p.r. Todistukset ovat samantapaisia kuin kolme aiempaa esimerkki\u00e4.<\/p>\n\n\n\nBinaaripuut<\/h3>\n\n\n\n
Merkkijonot ja unionit<\/h3>\n\n\n\n
Objektit<\/h3>\n\n\n\n
{\n \"auto\": 6,\n \"polkupy\u00f6r\u00e4: 12,\n \"moottoripy\u00f6r\u00e4\": (18,17)\n}<\/code><\/pre>\n\n\n\nJohtop\u00e4\u00e4t\u00f6s<\/h2>\n\n\n\n