Arvutatavuse teooria

Arvutavuse teooria, tuntud ka kui rekursiivse funktsiooni teooria, on matemaatilise loogika haru, mis uurib algoritmide ja nendega seotud arvutusseadmete omadusi. See on arvutiteaduse alus ja on tihedalt seotud teiste teoreetilise arvutiteaduse teooriatega, nagu keerukusteooria ja algoritmilise teabe teooria.

Arvutavuse teooria aluseks on Church-Turingi tees, mis väidab, et funktsioon on arvutatav siis ja ainult siis, kui seda saab arvutada Turingi masina abil. Arvutusfunktsioon on mis tahes algoritm, valem või reegel, mida saab arvutis kirjutada ja hinnata. Kõik arvutites kasutatavad algoritmid põhinevad arvutatavuse teoorial.

Teooria töötasid välja mitmed erinevad uurijad, alustades Alan Turingi töödega 1930. aastatel. 1950. aastate lõpuks oli teooria hästi arenenud ja seda rakendati ka muudes valdkondades, nagu automaatide teooria, programmeerimiskeeled ja tehisintellekt. Arvutustehnoloogia arenedes on arenenud ka arvutatavuse teooria teooriad ja rakendused.

Arvutusteooriat kasutatakse algoritmide keerukuse ja nende lahendamise viiside analüüsimiseks, samuti arvutite piirangute mõistmiseks. Seda kasutatakse ka algoritmide õigsuse tõestamiseks. Lõpuks kasutatakse seda funktsioonide ja predikaatide väljendamise ja arvutamise piirangute uurimiseks.