Laskettavuuden teorian perusteet ja Churchin teesi
PIIRTO, JUHO (2007)
PIIRTO, JUHO
2007
Matematiikka - Mathematics
Informaatiotieteiden tiedekunta - Faculty of Information Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2007-05-04
Julkaisun pysyvä osoite on
https://urn.fi/urn:nbn:fi:uta-1-16791
https://urn.fi/urn:nbn:fi:uta-1-16791
Tiivistelmä
Tämän työn aiheena on laskettavuuden teorian perusteet. Tarkoituksenani on ensinnäkin pohtia hieman mitä tarkoitetaan "laskemisella" ja kuinka laskemiseksi luokiteltava prosessi on formalisoitavissa. Esittelen rajoittamattoman rekisterikoneen, osittainrekursiiviset funktiot ja Turingin koneen, jotka ovat vaihtoehtoisia tapoja formalisoida laskeminen. Työn lopullisena tavoitteena on osoittaa, että näiden kolmen järjestelmän kautta määriteltyjen laskettavien funktioiden joukot ovat yhtäpitäviä, ja yleistää tämä tulos niinsanottuun Churchin teesiin, jonka mukaan kaikki mahdolliset laskettavuuden käsitteen formaalit määritelmät antavat yhtäpitävät laskettavien funktioiden joukot.
Päälähteenäni olen käyttänyt Nigel Cutlandin kirjaa Computability, lukuunottamatta lukua 4, jossa olen käyttänyt Piergiorgio Odifreddin kirjaa Classical Recursion Theory.
Asiasanat: laskettavuuden teoria, Churchin teesi
Päälähteenäni olen käyttänyt Nigel Cutlandin kirjaa Computability, lukuunottamatta lukua 4, jossa olen käyttänyt Piergiorgio Odifreddin kirjaa Classical Recursion Theory.
Asiasanat: laskettavuuden teoria, Churchin teesi