Laskettavuusteoria
Siirry navigaatioon
Siirry hakuun
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[muokkaa | muokkaa wikitekstiä]
Lähteet[muokkaa | muokkaa wikitekstiä]
- ↑ Computability and Complexity plato.stanford.edu. 24.6.2004. Viitattu 29.4.2024. (englanniksi)
- ↑ T. Rado: On Non-Computable Functions (PDF) archive.org. 12.11.1961. Viitattu 29.4.2024. (englanniksi)