Arvutuslikkus

Arvutuslikkus on matemaatika ja informaatika valdkond, mis uurib, milliseid probleeme saab lahendada algoritmide abil. Probleem on arvutuslikult lahendatav, kui selle lahendamiseks on olemas lõplik juhis ehk algoritm, mis võtab iga sisendi ja väljastab õige vastuse lõpuks.

Peamised mudelid on Turingi masin, rekursiivsed funktsioonid ja lambda-kalkulus. Need formaalsed süsteemid on tihti vahetatult ekvivalentsed: kui funktsioon on lahendatav efektiivse meetodi abil, saab selle lahendada ühel neist mudelitest. Church-Turingi teoreem ütleb, et iga efektiivse meetodi abil arvutatav funktsioon on teostatav kas Turingi masinaga, rekursiivsete funktsioonide või lambda-kalkulusega.

Olulised mõisted hõlmavad otsustatavust ja otsustamatust. Otsustatav probleem saab lahendada lõpliku algoritmiga; otsustamatu probleem ei saa. Näide: lõpetamise probleem – antud programm ja sisend, kas programm lõpetab, on otsustamatu. Arvutuslikkus näitab seega, et on probleeme, mida ei ole võimalik lahendada üldise algoritmiga, hoolimata sellest, kui palju aega või ressursse antakse. Teadlased uurivad ka piiranguid, mis tulenevad mudelitest ja matemaatilistest tõestustest, ning eristavad lisaks veel erinevaid klassifikatsioone, nagu rekursiivselt lahendatavad ja mitte-lahendatavad probleemid.