Lukuteoreettiset funktiot

Laskettavat, mutta ei primitiivirekursiiviset funktiot

Viime artikkelissa käsittelimme primitiivirekursiivisia funktioita ja totesimme, kuinka melkein kaikki tavanomaiset tietokoneella laskettavissa olevat funktiot ja operaattorit, olivat nämä sitten kokonaislukujen, murtolukujen, lukulistojen tai merkkijonojen operaatioita, ovat Gödel-numeroinnin ansiosta primitiivirekursiivisia. Tämä ei kuitenkaan tarkoita, että kaikki laskettavissa olevat funktiot olisivat primitiivirekursiivisia. Primitiivirekursiivisille funktioille on ominaista erityisesti, että kaikki silmukat ovat määrämittaisia, koska rekursiosäännössä käydään läpi korkeintaan luvut väliltä 0..n-1. Mitkään operaatiot, joissa tarvitaan potentiaalisesti ikisilmukkaa tai määrittelemättömän pituista silmukkaa eivät voi olla primitiivirekursiivisia. Esimerkiksi lukujen kuuluminen johonkin fraktaaliin kuten Mandelbrotin joukkoon tai Julian joukkoihin, lasketaan ei-määrämittaisella iteraatiolla ja tarkkaa tietoa kompleksiluvun joukkoon kuulumisesta ei voi määritellä niin, että voitaisiin sitoutua tiettyyn silmukan pituuden ylärajaan. Nämä operaatiot ovat laskettavia, mutta eivät ole p.r.

Ackermann-Péter-funktio

Tunnettu yksinkertaisen näköinen funktio, joka voidaan määritellä ”tuplarekursiosäännöllä”, eli Ackermann-Péter-funktio:
$$
\left\{
\begin{array}{ccl}
A(0,n) & = & n+1 \\
A(m,0) & = & A(m-1,1),\quad m>0 \\
A(m,n) & = & A(m-1,A(m,n-1)),\quad m,n>0
\end{array}
\right.
$$
ei ole primitiivirekursiivinen.

Tämä funktio kasvaa uskomattoman nopeasti, kun $m>3$. Luvut ovat potenssitorneja, joiden kuvaama luku saattaa ylittää maailmankaikkeuden atomien lukumäärän ja kohota yhä korkeammalle sisäkkäisiin potenssitorneihin asti. Se, ettei AP-funktio ole p.r. johtuu siitä, että kaikilla p.r. funktioilla $f(\vec{x})$ on olemassa luku $m$ siten, että $A(m,\max(\vec{x}))>f(\vec{x})$. Todistus menee niin, että ensinnä todetaan nollafunktion, seuraajan ja projektioiden kasvavan hitaammin kuin AP-funktio, sen jälkeen todistetaan, että yhdistäminen tai primitiivirekursio eivät tätä asianlaitaa muuta. Todistus tähän on esitetty esimerkiksi Planetmath:in sivustolla.

Rajoittamaton minimalisaatio

Primitiivirekursiivisten funktioiden perhe voidaan laajentaa lukuteoreettisten eli $\mu$-rekursiivisten funktioiden perheeksi ottamalla käyttöön joku ikisilmukan mahdollistava rajaton rekursio-operaattori tai rajaton hakuoperaattori. Yksinkertaisin vaihtoehto on sallia rajoittamaton minimalisaatio. $f$ on saatu rajoittamattomalla minimalisaatiolla $g$:stä, jos
$$
f(\vec{x})=\mu n\ g(n,\vec{x})=0
$$
eli $f$:n arvo on pienin $n$ siten, että $g$:n arvo on $0$, $0$ muuten. Merkitään myös $f=(\mu g)$.

Universaali lukuteoreettinen funktio ja ratkeamattomuus

Seuraavassa tekstissä todistetaan kaksi tärkeää teoreemaa, Kleenen normaalimuototeoreema ja sen johdannaisena Gödelin lukuteorian epäsäännöllisyyslause. Kleenen normaalimuototeoreema sanoo, että kaikki lukuteoreettiset funktiot voidaan sieventää muotoon $f=(\gamma g(\mu h))$, jossa $g$ ja $h$ ovat p.r. eli rajoittamatonta minimalisaatiota tarvitsee käyttää korkeintaan kerran. Gödelin lukuteorian epätäydellisyyslause sanoo, että ei ole mitään yleistä algoritmia, jolla voitaisiin luotettavasti määrittää, onko lukuteoreettisella funktiolla $g(n,\vec{x})=0$ ratkaisua $n$. Tämä muotoiltiin alunperin muodossa, että ei ole olemassa predikaattilogiikan kaavaa, jolla voitaisiin todeta toisesta predikaattilogiikan kaavasta, onko sillä mallia, eli muuttujien sijoitusta, jolla lause olisi tosi, mutta tässä mainittu versio on sen kanssa yhtäpitävä.

Universaali lukuteoreettinen funktio

Yllä olevien tulosten todistamiseksi tarvitaan universaali lukuteoreettinen funktio
$$
\psi(\langle f\rangle,\langle\vec{x}\rangle)=y
$$
jolla on ominaisuus, että se ottaa parametreikseen kaksi lukua: funktion $f$ Gödel-numeron ja sen parametrien $\vec{x}$ Gödel-numeron, joka muuten on edellisen artikkelimme mukainen linkitetty lista. Tällainen funktio ei voi tietenkään olla primitiivirekursiivinen, mutta se on todistettavissa lukuteoreettiseksi. Tärkein havainto on, että n.s. Kleenen $T$-predikaatti, joka varmistaa, onko lukuteoreettisen funktion laskenta suoritettu oikein, on p.r. $T$-predikaatti-määritellään:
$$
T(c,\langle f\rangle,\langle\vec{x}\rangle)
$$
on tosi, jos $c=\mathrm{cons}(y,\mathrm{cons}(\langle f\rangle,\langle\vec{x}\rangle))$ ja $f(\vec{x})=y$, epätosi muuten. Tällöinhän voidaan päätellä, että:
$$
\psi(\langle f\rangle,\langle\vec{x}\rangle)=\mathrm{car}(\mu c\ T(c,\langle f\rangle,\langle\vec{x}\rangle))
$$
jolloin rajoittamaton minimalisaatio hakee ensin laskennan $c$ ja erottelee siitä varsinaisen vastauksen parin vasemmalta puolelta $\mathrm{car}$-operaatiolla. Edelläoleva kaava on myös Kleenen normaalimuodon mukainen, joten jäljellä on muodostaa lukuteoreettisten funktioiden Gödel-numerointi ja todistaa, että $T$ on p.r.

Lukuteoreettisten funktioiden Gödel-numerointi

Sovitaan, että $\zeta$:a eli nollafunktiota vastaa luku $n=0$ ja $\sigma$:a eli seuraajaa vastaa luku $n=1$. Jos luku on tätä suurempi, tarkastellaan lukua $n-2$ ja sen jakojäännöstä luvun $4$ kanssa. Tällöin olkoon:
$$
(n-2)\%4=
\left\{
\begin{array}{ccl}
0 & : & \pi \\
1 & : & \gamma \\
2 & : & \rho \\
3 & : & \mu
\end{array}
\right.
$$
eli $0$ on projektio, $1$ on yhdistäminen, $2$ on primitiivirekursio ja $3$ on rajoittamaton minimalisaatio. Nämä operaatiot vaativat tuekseen ylimääräistä dataa, jonka on löydyttävä koodattuna osamäärään:
$$
\phi=\frac{n-2}{4}
$$
Projektion tapauksessa tarvitaan vähintään tieto, monesko alkio (nollasta alkaen) projisoidaan listasta. Tällöin $\phi$ on ei-negatiivinen kokonaisluku, joka kertoo tämän tiedon.
Yhdistämisen tapauksessa tarvitaan pari, jossa vasemmalla puolella on funktio $g$ ja oikealla puolella lista $\vec{h}$ koodattuna vastaamaan tapausta $f=(\gamma g\vec{h})$. Edellisen artikkelin perusteella tällaisten parien ja listojen koostaminen funktioiden $g$ ja $\vec{h}$ Gödel-numeroista on p.r.
Primitiivirekursion tapauksessa $f=(\rho gh)$ tarvitaan vain pari $\phi=\mathrm{cons}(\langle g\rangle,\langle h\rangle)$, joka on p.r.
Minimalisaation tapauksessa $f=(\mu g)$ tarvitaan lopulta vain funktion $g$ Gödel-numero $\langle g\rangle$. Lukuteoreettisten funktioiden Gödel-numerointi on siis p.r. $\Box$
On hyvä huomata, että listojen ulkopuolelta projisoidessa voidaan tehdä yleisyyttä loukkaamatta oletus, että palautetaan $0$ ja jos yhdistämisessä, primitiivirekursiossa tai minimalisaatiossa funktioiden argumenttien lukumäärä ei täsmää, voidaan puuttuvat argumentit olettaa arvoiksi $0$ ja ylimääräiset argumentit hylätä. Tämä johtuu edellisen artikkelin kohdasta, joka käsittelee eksplisiittistä transformaatiota.

Nollafunktion, seuraajan ja projektion $T$-predikaatti

Nollafunktion $\zeta$ $T$-predikaatti $T(\mathrm{cons}(0,\mathrm{cons}(0,\langle\vec{x}\rangle)),0,\langle\vec{x}\rangle)$ on selkeästi p.r. Jatkossa tarkastellaan vain laskennan $c$ vasemman puolen konstruktiota, koska $\langle f\rangle$ ja $\langle\vec{x}\rangle$ ovat itsestäänselvästi p.r. edellisen kappaleen ja artikkelin nojalla. Seuraajafunktion $\sigma$ $T$-predikaatti on myös p.r. koska $\mathrm{cons}(n+1,\mathrm{cons}(1,\langle[n]\rangle))$ on p.r. Projektio on p.r. koska edellisessä artikkelissa todistimme, että $n$:nnen alkion projisointi listasta on p.r. (yksityiskohdat $T$-predikaatin muodostamisessa sivuutetaan).

Yhdistämisen, primitiivirekursion ja minimalisaation $T$-predikaatit

Näissä todistuksissa joudutaan tietenkin olettamaan, että viitattavien funktioiden $T$-predikaatit on jo todistettu primitiivirekursiivisiksi. $(\gamma g\vec{h})$:n $T$-predikaatti on p.r. koska ehto:
$$
(\forall[n<\mathrm{len}(\langle\vec{h}\rangle)]\ h_n(\vec{x})=y_n) \land g(\vec{y})=x
$$
on p.r. jos $T_g$ ja kaikki $T_\vec{h}$ myös ovat. $T_{(\rho gh)}$ on p.r. koska ehto:
$$
v_0=g(\vec{x}) \land(\forall[k<n]v_k=h(k-1,v_{k-1},\vec{x}))
$$
on samoilla ehdoilla. Lopulta $T_{(\mu g)}$ on p.r. jos $T_g$ on, koska ehto:
$$
(f(y,\vec{x})=0)\land (\forall[n<y]\ f(n,\vec{x})>0)
$$
on p.r. Kaikkien lukuteoreettisten funktioiden $T$-predikaatit ovat siis p.r. ja samalla on myös yllämainittu Kleenen normaalimuototeoreema todistettu ja universaali lukuteoreettinen funktio
$$
\psi(\langle f\rangle,\langle\vec{x}\rangle)=y
$$
minkä tahansa lukuteoreettisen funktion arvon evaluoimiseksi käytössä.

Ratkeamattomat ongelmat ja lukuteorian epätäydellisyyslause

Koska universaali lukuteoreettinen funktio ja Gödel-numerointi mahdollistavat funktiot ja kaavat, joille voidaan antaa parametreiksi muita funktioita ja kaavoja, on mahdollista luoda myös funktioita ja kaavoja, jotka tutkivat itseään tai itseään hieman muunneltuina. Tällöin voidaan saada aikaan erilaisia paradokseja ja ristiriitoja, jotka osoittavat, että tietyt matemaattiset ja tietotekniset ongelmat ovat ohjelmallisesti ja loogisesti ratkeamattomia. Oletetaan, että olisi olemassa predikaatti $M$, jolla voitaisiin tarkastaa funktiosta $f$, onko olemassa arvoa $n$ siten, että $f(n,\vec{x})=0$ eli $M(\langle f\rangle)$, jos tällainen nollakohta on. Predikaattihan on on tosi, jos sen karakteristinen funktio on $1$ ja epätosi, jos karakteristinen funktio on $0$. Mitä on $M(\langle M_f \rangle)$? Nyt $M$ on tosi, jos $M_f=0$, eli $M$ on tosi, jos $M$ on epätosi. Tämä on ristiriita ja ei siis voi olla olemassa tällaista asiaa tutkivaa predikaattia tai funktiota, joka toimisi yleispätevästi. Tämä ja sen johdannaiset tunnetaan esimerkiksi Gödelin lukuteorian epätäydellisyyslauseena tai Turingin koneen pysähtymisongelmana.