Todistus<\/a> t\u00e4h\u00e4n on esitetty esimerkiksi Planetmath:in sivustolla.<\/p>\n\n\n\nRajoittamaton minimalisaatio<\/h3>\n\n\n\n
Primitiivirekursiivisten funktioiden perhe voidaan laajentaa lukuteoreettisten eli $\\mu$-rekursiivisten funktioiden perheeksi ottamalla k\u00e4ytt\u00f6\u00f6n joku ikisilmukan mahdollistava rajaton rekursio-operaattori tai rajaton hakuoperaattori. Yksinkertaisin vaihtoehto on sallia rajoittamaton minimalisaatio. $f$ on saatu rajoittamattomalla minimalisaatiolla $g$:st\u00e4, jos
$$
f(\\vec{x})=\\mu n\\ g(n,\\vec{x})=0
$$
eli $f$:n arvo on pienin $n$ siten, ett\u00e4 $g$:n arvo on $0$, $0$ muuten. Merkit\u00e4\u00e4n my\u00f6s $f=(\\mu g)$.<\/p>\n\n\n\n
Universaali lukuteoreettinen funktio ja ratkeamattomuus<\/h2>\n\n\n\n
Seuraavassa tekstiss\u00e4 todistetaan kaksi t\u00e4rke\u00e4\u00e4 teoreemaa, Kleenen normaalimuototeoreema ja sen johdannaisena G\u00f6delin lukuteorian ep\u00e4s\u00e4\u00e4nn\u00f6llisyyslause. Kleenen normaalimuototeoreema sanoo, ett\u00e4 kaikki lukuteoreettiset funktiot voidaan sievent\u00e4\u00e4 muotoon $f=(\\gamma g(\\mu h))$, jossa $g$ ja $h$ ovat p.r. eli rajoittamatonta minimalisaatiota tarvitsee k\u00e4ytt\u00e4\u00e4 korkeintaan kerran. G\u00f6delin lukuteorian ep\u00e4t\u00e4ydellisyyslause sanoo, ett\u00e4 ei ole mit\u00e4\u00e4n yleist\u00e4 algoritmia, jolla voitaisiin luotettavasti m\u00e4\u00e4ritt\u00e4\u00e4, onko lukuteoreettisella funktiolla $g(n,\\vec{x})=0$ ratkaisua $n$. T\u00e4m\u00e4 muotoiltiin alunperin muodossa, ett\u00e4 ei ole olemassa predikaattilogiikan kaavaa, jolla voitaisiin todeta toisesta predikaattilogiikan kaavasta, onko sill\u00e4 mallia, eli muuttujien sijoitusta, jolla lause olisi tosi, mutta t\u00e4ss\u00e4 mainittu versio on sen kanssa yht\u00e4pit\u00e4v\u00e4.<\/p>\n\n\n\n
Universaali lukuteoreettinen funktio<\/h3>\n\n\n\n
Yll\u00e4 olevien tulosten todistamiseksi tarvitaan universaali lukuteoreettinen funktio
$$
\\psi(\\langle f\\rangle,\\langle\\vec{x}\\rangle)=y
$$
jolla on ominaisuus, ett\u00e4 se ottaa parametreikseen kaksi lukua: funktion $f$ G\u00f6del-numeron ja sen parametrien $\\vec{x}$ G\u00f6del-numeron, joka muuten on edellisen artikkelimme mukainen linkitetty lista. T\u00e4llainen funktio ei voi tietenk\u00e4\u00e4n olla primitiivirekursiivinen, mutta se on todistettavissa lukuteoreettiseksi. T\u00e4rkein havainto on, ett\u00e4 n.s. Kleenen $T$-predikaatti, joka varmistaa, onko lukuteoreettisen funktion laskenta suoritettu oikein, on p.r. $T$-predikaatti-m\u00e4\u00e4ritell\u00e4\u00e4n:
$$
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\u00e4tosi muuten. T\u00e4ll\u00f6inh\u00e4n voidaan p\u00e4\u00e4tell\u00e4, ett\u00e4:
$$
\\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<\/em> $c$ ja erottelee siit\u00e4 varsinaisen vastauksen parin vasemmalta puolelta $\\mathrm{car}$-operaatiolla. Edell\u00e4oleva kaava on my\u00f6s Kleenen normaalimuodon mukainen, joten j\u00e4ljell\u00e4 on muodostaa lukuteoreettisten funktioiden G\u00f6del-numerointi ja todistaa, ett\u00e4 $T$ on p.r.<\/p>\n\n\n\nLukuteoreettisten funktioiden G\u00f6del-numerointi<\/h3>\n\n\n\n
Sovitaan, ett\u00e4 $\\zeta$:a eli nollafunktiota vastaa luku $n=0$ ja $\\sigma$:a eli seuraajaa vastaa luku $n=1$. Jos luku on t\u00e4t\u00e4 suurempi, tarkastellaan lukua $n-2$ ja sen jakoj\u00e4\u00e4nn\u00f6st\u00e4 luvun $4$ kanssa. T\u00e4ll\u00f6in 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\u00e4minen, $2$ on primitiivirekursio ja $3$ on rajoittamaton minimalisaatio. N\u00e4m\u00e4 operaatiot vaativat tuekseen ylim\u00e4\u00e4r\u00e4ist\u00e4 dataa, jonka on l\u00f6ydytt\u00e4v\u00e4 koodattuna osam\u00e4\u00e4r\u00e4\u00e4n:
$$
\\phi=\\frac{n-2}{4}
$$
Projektion tapauksessa tarvitaan v\u00e4hint\u00e4\u00e4n tieto, monesko alkio (nollasta alkaen) projisoidaan listasta. T\u00e4ll\u00f6in $\\phi$ on ei-negatiivinen kokonaisluku, joka kertoo t\u00e4m\u00e4n tiedon.
Yhdist\u00e4misen 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\u00e4llaisten parien ja listojen koostaminen funktioiden $g$ ja $\\vec{h}$ G\u00f6del-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\u00f6del-numero $\\langle g\\rangle$. Lukuteoreettisten funktioiden G\u00f6del-numerointi on siis p.r. $\\Box$
On hyv\u00e4 huomata, ett\u00e4 listojen ulkopuolelta projisoidessa voidaan tehd\u00e4 yleisyytt\u00e4 loukkaamatta oletus, ett\u00e4 palautetaan $0$ ja jos yhdist\u00e4misess\u00e4, primitiivirekursiossa tai minimalisaatiossa funktioiden argumenttien lukum\u00e4\u00e4r\u00e4 ei t\u00e4sm\u00e4\u00e4, voidaan puuttuvat argumentit olettaa arvoiksi $0$ ja ylim\u00e4\u00e4r\u00e4iset argumentit hyl\u00e4t\u00e4. T\u00e4m\u00e4 johtuu edellisen artikkelin kohdasta, joka k\u00e4sittelee eksplisiittist\u00e4 transformaatiota.<\/p>\n\n\n\n
Nollafunktion, seuraajan ja projektion $T$-predikaatti<\/h3>\n\n\n\n
Nollafunktion $\\zeta$ $T$-predikaatti $T(\\mathrm{cons}(0,\\mathrm{cons}(0,\\langle\\vec{x}\\rangle)),0,\\langle\\vec{x}\\rangle)$ on selke\u00e4sti p.r. Jatkossa tarkastellaan vain laskennan $c$ vasemman puolen konstruktiota, koska $\\langle f\\rangle$ ja $\\langle\\vec{x}\\rangle$ ovat itsest\u00e4\u00e4nselv\u00e4sti p.r. edellisen kappaleen ja artikkelin nojalla. Seuraajafunktion $\\sigma$ $T$-predikaatti on my\u00f6s p.r. koska $\\mathrm{cons}(n+1,\\mathrm{cons}(1,\\langle[n]\\rangle))$ on p.r. Projektio on p.r. koska edellisess\u00e4 artikkelissa todistimme, ett\u00e4 $n$:nnen alkion projisointi listasta on p.r. (yksityiskohdat $T$-predikaatin muodostamisessa sivuutetaan).<\/p>\n\n\n\n
Yhdist\u00e4misen, primitiivirekursion ja minimalisaation $T$-predikaatit<\/h3>\n\n\n\n
N\u00e4iss\u00e4 todistuksissa joudutaan tietenkin olettamaan, ett\u00e4 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\u00f6s 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\u00f6s yll\u00e4mainittu Kleenen normaalimuototeoreema todistettu ja universaali lukuteoreettinen funktio
$$
\\psi(\\langle f\\rangle,\\langle\\vec{x}\\rangle)=y
$$
mink\u00e4 tahansa lukuteoreettisen funktion arvon evaluoimiseksi k\u00e4yt\u00f6ss\u00e4.<\/p>\n\n\n\n
Ratkeamattomat ongelmat ja lukuteorian ep\u00e4t\u00e4ydellisyyslause<\/h3>\n\n\n\n
Koska universaali lukuteoreettinen funktio ja G\u00f6del-numerointi mahdollistavat funktiot ja kaavat, joille voidaan antaa parametreiksi muita funktioita ja kaavoja, on mahdollista luoda my\u00f6s funktioita ja kaavoja, jotka tutkivat itse\u00e4\u00e4n tai itse\u00e4\u00e4n hieman muunneltuina. T\u00e4ll\u00f6in voidaan saada aikaan erilaisia paradokseja ja ristiriitoja, jotka osoittavat, ett\u00e4 tietyt matemaattiset ja tietotekniset ongelmat ovat ohjelmallisesti ja loogisesti ratkeamattomia. Oletetaan, ett\u00e4 olisi olemassa predikaatti $M$, jolla voitaisiin tarkastaa funktiosta $f$, onko olemassa arvoa $n$ siten, ett\u00e4 $f(n,\\vec{x})=0$ eli $M(\\langle f\\rangle)$, jos t\u00e4llainen nollakohta on. Predikaattihan on on tosi, jos sen karakteristinen funktio on $1$ ja ep\u00e4tosi, jos karakteristinen funktio on $0$. Mit\u00e4 on $M(\\langle M_f \\rangle)$? Nyt $M$ on tosi, jos $M_f=0$, eli $M$ on tosi, jos $M$ on ep\u00e4tosi. T\u00e4m\u00e4 on ristiriita ja ei siis voi olla olemassa t\u00e4llaista asiaa tutkivaa predikaattia tai funktiota, joka toimisi yleisp\u00e4tev\u00e4sti. T\u00e4m\u00e4 ja sen johdannaiset tunnetaan esimerkiksi G\u00f6delin lukuteorian ep\u00e4t\u00e4ydellisyyslauseena tai Turingin koneen pys\u00e4htymisongelmana.<\/p>\n","protected":false},"excerpt":{"rendered":"
Laskettavat, mutta ei primitiivirekursiiviset funktiot Viime artikkelissa k\u00e4sittelimme primitiivirekursiivisia funktioita ja totesimme, kuinka melkein kaikki tavanomaiset tietokoneella laskettavissa olevat funktiot ja operaattorit, olivat n\u00e4m\u00e4 sitten kokonaislukujen, murtolukujen, lukulistojen tai merkkijonojen operaatioita, ovat G\u00f6del-numeroinnin ansiosta primitiivirekursiivisia. T\u00e4m\u00e4 ei kuitenkaan tarkoita, ett\u00e4 kaikki laskettavissa olevat funktiot olisivat primitiivirekursiivisia. Primitiivirekursiivisille funktioille on ominaista…<\/p>\n","protected":false},"author":2,"featured_media":234,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7,4],"tags":[],"class_list":["post-216","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-korkeakoulu","category-matematiikka"],"_links":{"self":[{"href":"http:\/\/tslespoo.fi\/wordpress\/wp-json\/wp\/v2\/posts\/216","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/tslespoo.fi\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/tslespoo.fi\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/tslespoo.fi\/wordpress\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/tslespoo.fi\/wordpress\/wp-json\/wp\/v2\/comments?post=216"}],"version-history":[{"count":16,"href":"http:\/\/tslespoo.fi\/wordpress\/wp-json\/wp\/v2\/posts\/216\/revisions"}],"predecessor-version":[{"id":263,"href":"http:\/\/tslespoo.fi\/wordpress\/wp-json\/wp\/v2\/posts\/216\/revisions\/263"}],"wp:featuredmedia":[{"embeddable":true,"href":"http:\/\/tslespoo.fi\/wordpress\/wp-json\/wp\/v2\/media\/234"}],"wp:attachment":[{"href":"http:\/\/tslespoo.fi\/wordpress\/wp-json\/wp\/v2\/media?parent=216"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/tslespoo.fi\/wordpress\/wp-json\/wp\/v2\/categories?post=216"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/tslespoo.fi\/wordpress\/wp-json\/wp\/v2\/tags?post=216"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}