Laskettavuus

Wikipediasta
Siirry navigaatioon Siirry hakuun

Laskettavuus on teoreettisen tietojenkäsittelytieteen laskettavuusteorian haara, joka tutkii ongelmien ratkeavuutta algoritmisesti. Käytännössä laskettavuus tarkoittaa sitä, voidaanko jokin ongelma ratkaista tietokoneiden avulla vai ei. Laskettavuus on eri asia kuin laskennallinen vaativuus, jolla tarkoitetaan laskennallisen ongelman ratkaisemiseen tarvittavia resursseja kuten laskennan vaatimaa aikaa tai muistikapasiteettia.

Ongelmanasettelu on ensin muotoiltava täsmällisesti erilaisten laskennan mallien avulla, joiden voidaan ajatella olevan tietokoneiden matemaattisia malleja. Esimerkki tällaisesta mallista on Turingin kone. Vasta tämän jälkeen voidaan analysoida, onko se ylipäänsä ratkaistavissa.

Universaalin Turingin koneen käsite syntyi kun oli tarve esittää mitkä ongelmat olivat laskettavissa: ongelmat, joita universaalilla koneella ei voitu ratkaista eivät olleet laskettavissa.[1]

  1. Turing Machines plato.stanford.edu. Viitattu 7.2.2020. (englanniksi)

Aiheesta muualla

[muokkaa | muokkaa wikitekstiä]
Tämä tietotekniikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.