Laskettavat, mutta ei primitiivirekursiiviset funktiot Viime artikkelissa käsittelimme primitiivirekursiivisia funktioita ja totesimme, kuinka melkein kaikki tavanomaiset tietokoneella laskettavissa olevat funktiot ja operaattorit, olivat nämä sitten kokonaislukujen, murtolukujen, lukulistojen tai merkkijonojen operaatioita, ovat Gödel-numeroinnin ansiosta primitiivirekursiivisia. Tämä ei kuitenkaan tarkoita, että kaikki laskettavissa olevat funktiot olisivat primitiivirekursiivisia. Primitiivirekursiivisille funktioille on ominaista…

Yleistä 1900-luvun alkupuoli oli matemaattisen logiikan kulta-aikaa, jolloin suuret matemaatikot, kuten Alan Turing (1912-1954), Kurt Gödel (1906-1978), Alonzo Church (1903-1995), Emil Post (1897-1954) ja useat muut kehittivät useita matemaattisia malleja, jotka mallinsivat nykyaikaisia tietokoneita ennen kuin niitä oli varsinaisesti rakennettu. Samalla pystyttiin jo ennen tietokoneiden keksimistä päättelemään, mitä on tietokoneella…