Laskettavuus

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.

Katso myös

• Pysähtymisongelma
• P=NP
• Komputaatio
• Automaattiteoria
• Laskettavuusteoria
• Laskennallisen kompleksisuuden teoria

Aiheesta muualla

• Laskennan teoria (PDF) (englanniksi)