Browsing by Author "Kyyhkynen, Juho"

Tämän tutkielman päämäärä on osoittaa rekursiivisten funktioiden ja lambda-määriteltävien funktioiden yhtenevyys. Molemmat funktiojoukot ovat laskettavuuden teorian syntyyn vaikuttaneita laskennan malleja, joilla kuvataan automatisoitavissa olevia prosesseja. Kurt Gödel tarvitsi rekursiivisia funktioita predikaattilogiikan todistuvuuden mekanisointiin. Lambda-määriteltävyys taas pohjautuu Alonzo Churchin ideoimaan lambdalaskentaan (engl. lambda-calculus). Se koostuu funktioita esittävistä kaavoista, ja niille määritellyistä muunnossännöistä. Lambdalaskenta on toisinaan suomennettu myös lambdakalkyyliksi. Lambda-määriteltävät funktiot on rekursiivisten funktioiden ohella osoitettu yhteneviksi useiden muidenkin laskentaformalismien kanssa. Tämän johdosta on päädytty otaksumaan, että rekursiiviset operaatiot ovat ne, joita on ylipäänsä mahdollista realisoida jollain algoritmilla tai automaatiolla. Lambdalaskennan synnyinvuosien jälkeen hiljalleen kehittyi laskettavuuden teoria, jossa tutkitaan mitä tällaisilla mekaanisilla järjestelmillä, kuten tietokoneella, voi edes periaatteessa ratkoa. Luvussa 2 esitellään rekursiivisten funktioiden perhe sekä rekursiivisesti ratkeavat relaatiot. Aikaisempi tietämys matemaattisesta logiikasta ja rekursiivisista funktioista on hyödyksi, sillä kaikkien määritelmien semanttista oikeellisuutta ei käsitellä. Luvussa 3 esitellään lambdalaskennan lausekkeet ja muunnossäännöt sekä todistetaan Churchin-Rosserin lause, joka kuittaa lambda-laskennan toimivaksi laskentajärjestelmäksi. Lisäksi todistetaan lambdatermien kiintopistelause, jota vastaava tulos rekursiivisille funktioille on huomattavasti mutkikkaamman todistuksen takana. Aikaisempaa tietämystä lambdalaskennasta ei edellytetä. Luvussa 4 esitellään lambda-määriteltävien funktioiden joukko, joka viimeisessä luvussa osoitetaan samaksi rekursiivisten funktioiden joukon kanssa. Usein laskettavuuden teoriassa sallitaan osittaiset funktiot, joiden arvoa ei kaikissa pisteissä välttämättä ole määritelty. Tässä tutkielmassa käsitellään kuitenkin vain totaaleja funktioita.