Arvutatavuse

Arvutatavus ehk computability on mõiste, mis kirjeldab, milliseid funktsioone või probleeme saab lahendada algoritmiga. Kui olemas on lõplik algoritm või masin, mis antud sisendi korral tagastab õige väljundi (või otsustab lahendi) lõpuks, siis öeldakse, et see on arvutatav. Arvutatavus on ere teoreetiline alus arvutiteadustes ning aitab eristada loetamatuid probleeme neist, mida saab mehhaaniliselt lahendada.

Peamised arvutusmodelid hõlmavad Turingi masinat, lambda kalkulust ja rekursiivseid funktsioone. Nende ekvivalentsed mudelid annavad sama klassi arvutatavaid funktsioone, mis toob välja Church-Turingi teoreemi ideed: kui miski on arvutatav ühe mõistliku mudeli abil, on see arvutatav kõigis teistes sama mõistlikes mudelites. See teoreetik raam aitab mõista, milliseid ülesandeid saab üldse korraldada arvutamise teel.

Täielikult arvutatavus versus osaline arvutatavus. Täielikult arvutatav funktsioon on selline, mille jaoks on olemas algoritm, mis igal sisendil lõpeb ja annab õige väljundi. Osaliselt arvutatav (või osaliselt arvutatav funktsioon) tähendab, et on algoritm, mis annab väljundi kõikidel sisenditel, kus lahendus on olemas, kuid mõnel sisendil võib algoritm lõputult töötada. Sõltuvalt kontekstist eristatakse ka decidability ja semi-decidability.

Arvutatavus on fundamentaalne kontseptsioon teoreetilises informaatikas ja matemaatikas, ühendades algoritmide teooria, mõisted nagu deci? dokaz, ja kompleksus. See määrab piirid, mis on masinate jaoks praktikas saavutatav.