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
muokkaaLähteet
muokkaa- ↑ 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)