Laskettavuuden teorian perusteet ja Churchin teesi

Abstract

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