Laskettavuusteoria on matematiikan ja tietojenkäsittelytieteen alue, joka tutkii mitkä ongelmat voidaan laskennallisesti ratkaista. 1930-luvulla Gödel, Turing ja Church osoittivat, että kaikki ongelmat eivät ole laskennallisesti ratkaistavissa. Esimerkiksi Turingin koneiden opettamiseen suunniteltu "Busy Beaver" -peli ei ole laskennallisesti ratkaistavissa.
Katso myös Komputaatio Churchin–Turingin teesi Laskennallisen kompleksisuuden teoria
Lähteet
Luokka:Tietojenkäsittelyteoria Luokka:Matemaattinen logiikka