computability (tsz. computabilities)
Computability – magyarul: számíthatóság – a számítástudomány egyik alapfogalma, amely azt vizsgálja, milyen problémák oldhatók meg algoritmikusan. A számíthatóságelmélet (computability theory) annak megértésére törekszik, hogy milyen feladatokat képesek elvégezni a számítógépek, függetlenül a konkrét géptől vagy programnyelvtől.
Egy probléma akkor számítható, ha létezik egy algoritmus, amely véges idő alatt, véges lépésekben megoldást ad a bemenetre. Ez az algoritmus bármilyen megvalósítható program vagy eljárás lehet, amely determinisztikusan működik.
Modell | Jellemzők |
---|---|
Turing-gép | Elméleti gép, amely szalagot és állapotokat használ számításra. |
Lambda-kalkulus | Függvények absztrakciója és alkalmazása. |
RAM-gép | Egyszerű számítógépszerű modell. |
WHILE/LOOP nyelvek | Programozási nyelvi modellek számíthatóság leírására. |
Mindegyik modell ekvivalens számítási erejű: amit az egyik meg tud oldani, meg tudja a másik is.
Probléma típusa | Jelentés |
---|---|
Teljesen számítható | Létezik algoritmus, minden bemenetre megoldást ad. |
Részlegesen számítható | Létezik algoritmus, de nem minden bemenetre ad választ (pl. végtelen ciklus). |
Nem számítható | Nincs algoritmus, ami a problémát bármilyen bemenetre helyesen megoldaná. |
Vajon megáll-e egy tetszőleges program adott bemenetre?
Bizonyítottan nem eldönthető – nem létezik olyan algoritmus, amely minden esetben eldöntené.
Hilbert 10. problémája – nincs általános algoritmus, amely meghatározná, van-e egész megoldása.
Valami lehet számítható elméletileg, de gyakorlatilag kivitelezhetetlen, ha túl lassú (például exponenciális idejű algoritmus).
Ez vezet át a komplexitáselmélethez, amely a számítás erőforrásigényét vizsgálja (idő, memória).
A számíthatóság nemcsak a probléma természetétől, hanem a bemenet és kimenet kódolásától is függ. Például:
Egy probléma akkor számítható, ha visszavezethető (redukálható) egy másik, már ismert módon megoldható problémára.
Ez a fogalom fontos a teljesség és osztályozás szempontjából (pl. RE-teljes problémák).
Osztály | Leírás |
---|---|
Decidable (D) | Algoritmus létezik, mindig választ ad. |
Semi-decidable (RE) | Van algoritmus, ami megtalálja a megoldást, ha létezik, de nem feltétlenül jelez hibás bemenetet. |
Not RE | Még részlegesen sem számítható. |
A computability annak kérdését vizsgálja, hogy mi oldható meg algoritmikusan. Ez a számítástudomány egyik elméleti alapja, amely: