Laskettavuudesta

Abstract

Tässä tutkielmassa käsitellään laskettavuuden historiaa ja joitain perustuloksia. Laskettavuuden teoria perustuu matemaattisen logiikkaan, mutta 1930--luvulla siitä alkoi syntyä oma tieteenalansa laskennan mekanisointia mietittäessä. Eräs malli laskennan mekanisoinnista on tutkielmassakin käsiteltävä äärellinen automaatti, ja niihin liittyvät säännölliset kielet ja säännölliset lausekkeet. Äärellinen automaatti ei kuitenkaan ole tarkka algoritmi, koska sillä ei voida ratkaista kaikkia ratkaistavia ongelmia. Kielet ovat merkkijonojoukkoja, jotka voidaan tunnistaa automaatilla.

Turing-tunnistettavat ja ratkaistavat kielet liittyvät Turingin koneeseen. Turingin kone on eräs tarkan algoritmin määritelmä, eli kaikki ratkaistavat ongelmat voidaan ratkaista Turingin koneella. Kaikkia ongelmia ei kuitenkaan voida ratkaista ja ne ovat silloin ratkeamattomia. Kuuluisimpia niistä lienee universaalikielen ratkeamattomuus ja pysähtymisongelman ratkeamattomuus. Universaalikieli on kieli, joka sisältää tiedon kaikista binääriaakkoston tunnistettavista Turingin koneista. Pysähtymisongelmassa pyritään ratkaisemaan, pysähtyykö syötteenä annettu Turingin kone annetulla merkkijono syötteellä. Pysähtymisongelmasta ja yleensäkin ratkeavuudesta päästäisiin laskennanvaativuusteoriaan. Tässä tutkielmassa ei kuitenkaan käsitelty laskennanvaativuusteoriaa.

Asiasanat:laskettavuus, laskettavuuden teoria, Turingin kone, universaalikone, pysähtymisongelma, ratkeavuus