Hesablama nəzəriyyəsi (ing.Computational Theory) — riyaziyyat və kompüter elmlərinin bir sahəsidir və hesablama anlayışının əsaslarını, hesablama cihazlarının (məsələn, Türinq maşınları) nəzəri modelini, hesablama prosesinin gücünü və məhdudiyyətlərini öyrənir.[1] Bu nəzəriyyə, hansı problemlərin həll oluna biləcəyini və hansıların mümkün olmadığını müəyyən edir və hesablama mürəkkəbliyi kimi mövzuları əhatə edir.[2]
Hesablama nəzəriyyəsinin əsas bölmələri mövcuddur.[3]
Formal dillər, riyazi olaraq dilin sintaksisini və semantikasını müəyyən edən nəzəri modelləri araşdırır. Bu sahə, dilin hansı qaydalara əsasən formalaşdığını təhlil edir.[4]
Avtomatlar nəzəriyyəsi isə sadə hesablama modellərindən başlayaraq, daha mürəkkəb modellər yaratmağa imkan verən avtomatları tədqiq edir. Məsələn, sonlu avtomatlar, yığın avtomatları və Türinq maşınları.
Türinq maşınları və hesablana bilmə nəzəriyyəsi
Alan Türinqin təklif etdiyi Türinq maşını, hesablama nəzəriyyəsində universal hesablama modelidir. Bu model hesablana bilən funksiyaları müəyyən edir və bir məsələnin həll oluna bilib-bilməyəcəyini təhlil edir.
Hesablama mürəkkəbliyi nəzəriyyəsi
Bu nəzəriyyə hansı problemlərin nə dərəcədə resurslarla (vaxt və yaddaş) həll olunacağını müəyyənləşdirir.[5]
Məsələn, P (polinomial vaxtda həll olunan məsələlər) və NP (teyidi polinomial vaxtda edilə bilən məsələlər) sinifləri arasındakı fərqi öyrənir. NP-həlli çətin və ya həlli mümkün olmayan məsələlər də bu sahəyə daxildir.
Hesablama nəzəriyyəsində mürəkkəblik sinifləri (məsələn, P, NP, NP-tam, NP-mürəkkəb və s.) müxtəlif problemlərin həll mürəkkəbliyinə görə təsnif olunur.[7]
Hesablama nəzəriyyəsi kompüter elmlərinin nəzəri əsaslarını təşkil edir və real həyatda alqoritmlərin, kriptoqrafiyanın və maşın öyrənmənin inkişafında mühüm rol oynayır.
↑Gödel, Kurt. [Gödel (1946)] // Feferman, Solomon; və b. (redaktorlar ). Kurt Gödel Publications 1938–1974 Volume II. II. New York, USA: Oxford University Press. 1990. 144ff. ISBN978-0-19-514721-6. To be more precise: a function of integers is computable in any formal system containing arithmetic if and only if it is computable in arithmetic, where a function f is called computable in S if there is in S a computable term representing f. (NB. This volume also includes the 1946 paper by Kurt Gödel (with commentary by Charles Parsons at pp. 144ff.). This 1990 edition has the cited footnote added by Gödel on p. 150 (which had also been added to Gödel's reprint in Şablon:Citeref).)
Burgin, Mark; Klinger, Allen. "Experience, Generations, and Limits in Machine Learning". Theoretical Computer Science. 317 (1–3). 2004: 71–91. doi:10.1016/j.tcs.2003.12.005.
Friedberg, Richard M."Three theorems on recursive enumeration: I. Decomposition, II. Maximal Set, III. Enumeration without repetition". The Journal of Symbolic Logic. 23 (3). 1958: 309–316. doi:10.2307/2964290. JSTOR2964290.