Rekursiivisten ja lambda-määriteltävien funktioiden yhtenevyys

Show full item record



Permalink

http://urn.fi/URN:NBN:fi:hulib-201904011567
Title: Rekursiivisten ja lambda-määriteltävien funktioiden yhtenevyys
Author: Kyyhkynen, Juho
Contributor: University of Helsinki, Faculty of Science
Publisher: Helsingin yliopisto
Date: 2019
Language: fin
URI: http://urn.fi/URN:NBN:fi:hulib-201904011567
http://hdl.handle.net/10138/300762
Thesis level: master's thesis
Discipline: Matematiikan opettajan koulutus
Abstract: 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.


Files in this item

Total number of downloads: Loading...

Files Size Format View
Kyyhkynen_Juho_Pro_gradu_2019.pdf 585.1Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record