laskettavanatila

Laskettavanatila on käsite teoreettisessa tietojenkäsittelytieteessä, jota käytetään kuvaamaan tilaa laskentamallissa, jonka esiintyminen sekä tilan ominaisuuksien määrittely on mahdollista toteuttaa laskettavasti eli algoritmilla. Termi korostaa computability–näkökulmaa: laskettava tila on sellainen tila, jonka saavutettavuus, hyväksyntä tai muut olennaiset ominaisuudet voidaan päätellä päätöksentekijän tai siirtofunktion kautta.

Kontekstissa laskettavan tilan hahmotus liittyy automaatioteoriaan ja laskennan malleihin kuten finiteseihin automaateihin, Turingin koneisiin sekä muuttuviin ja epädeterministisiin malleihin. Yksinkertaisessa deterministisessä finitessä automaatissa kaikkia tiloja voidaan pitää laskettavina, koska tilat ja siirtymät ovat ennalta määriteltyjä. Laajemmissa malleissa laskettavuus voi koskea esimerkiksi sitä, voiko tilan saavuttamisen tai tilan hyväksynnän päätellä tehokkaasti.

Rajat ja huomioitavat seikat: joissakin kehittyneissä tai äärellisistä tiloista poikkeavissa malleissa voi esiintyä kysymyksiä, joita ei voi ratkaista ohjelmallisesti yleisellä tasolla. Esimerkiksi eri reputational tai rekursiivisesti määriteltyjen järjestelmien konteksteissa tilan saavutettavuuden päätteleminen voi olla koodin ulkopuolella epävarmaa tai ratkaisematta.

Sovellukset: laskettavan tilan käsite on osa muodollista menetelmää, mallintamista, ohjelmistotarkastusta ja virheiden ehkäisyä. Sille on käyttöä esimerkiksi ohjelmistojen käyttäytymisen verifioinnissa sekä järjestelmien oikeellisuuden osoittamisessa, kun halutaan varmistaa, että tietyt tilat ovat laskettavasti saavutettavissa ja määriteltävissä.