Laskettavuusteoria
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.[1] Esimerkiksi Turingin koneiden opettamiseen suunniteltu "Busy Beaver" -peli ei ole laskennallisesti ratkaistavissa.[2]
Katso myös
- Komputaatio
- Churchin–Turingin teesi
- Laskennallisen kompleksisuuden teoria