arvutatavust

Arvutatavus on teoreetilise arvutusteaduse mõiste, mis käsitleb, kas mingi funktsioon või probleem saab lahendada lõpliku algoritmiga. Üldiselt tähendab arvutatavus, et on olemas samm-sammuline protsess, mis igale lubatud sisendile annab õige väljundi ja lõpeb pärast viimast sammu.

Peamised arvutuse mudelid on Turingi masin, lambda kalkul ja rekursiivsed funktsioonid; need mudelid on teoreetiliselt võrdväärsed. Church–Turingi teooria kohaselt kirjeldavad need mudelid sama ulatust arvutatavusest, ning seetõttu on neil keelatud öelda, mis funktsioonid on arvutatavad.

Otsustatavus ja mittotsustatavus on arvutatavuse põhikategooriad. Keele L ⊆ Σ* puhul on see otsustatav, kui selle jaoks on Turingi masin, mis iga sisendi korral lõpetab ja otsustab kuuluvuse (jah või ei). Mitte kõik keeled ei ole otsustatavad. Rekursiivselt loetavad keeled (RE-keeled) on keeled, mille jaoks on Turingi masin, mis lõpetab ja aktsepteerib iga kuuluvat sisendit, kuid võib mitte lõpetada mittekuuluva puhul. Halvingi (peatumise) probleem on kuulus näide mittotsustatavast probleemist.

Arvutatavuse teoorial on oluline roll programmeerimise keelade ja formaliseerimise fundamentides ning see piiritleb, millised probleemid on võimalik automatiseerida ja millised jäävad teoreetiliste piiride taha. Church–Turingi tees pakub üldist raamistikku mõistmaks arvutamise põhitõdesid ja piiranguid.