Hesablama nəzəriyyəsi

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]

Əsas bölmələri

Formal dillər və avtomatlar nəzəriyyəsi
- 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.
Alqoritm və mürəkkəblik sinifləri ^[6]
- 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.

İstinadlar

↑ 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. ISBN 978-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).)
↑ Soare, Robert Irving. "Computability Theory and Applications: The Art of Classical Computability" (PDF). Department of Mathematics. University of Chicago. 2011-12-22. 2022-06-30 tarixində arxivləşdirilib (PDF). İstifadə tarixi: 2017-08-23.
↑ Friedman, Harvey. "Renaming recursion theory". FOM email list. 1998-08-28. 2022-03-01 tarixində arxivləşdirilib. İstifadə tarixi: 2006-01-09.
↑ Radó, Tibor. "On non-computable functions". Bell System Technical Journal. 41 (3). May 1962: 877–884. doi:10.1002/j.1538-7305.1962.tb00480.x.
↑ Kleene, Stephen Cole. Introduction to Metamathematics. North-Holland. 1952. 300, 376. ISBN 0-7204-2103-9.
↑ Simpson, Stephen George. "What is computability theory?". FOM email list. 1998-08-24. 2021-12-18 tarixində arxivləşdirilib. İstifadə tarixi: 2006-01-09.
↑ Fortnow, Lance Jeremy. "Is it Recursive, Computable or Decidable?". 2004-02-15. 2022-08-07 tarixində arxivləşdirilib. İstifadə tarixi: 2018-03-22.

Ədəbiyyat

Bakalavr səviyyəli mətnlər

Cooper, S. Barry. Computability Theory. Chapman & Hall/CRC. 2004. ISBN 1-58488-237-9.
Matiyasevich, Yuri Vladimirovich. Hilbert's Tenth Problem. MIT Press. 1993. ISBN 0-262-13295-8.

Təkmilləşdirilmiş mətnlər

Jain, Sanjay; Osherson, Daniel Nathan; Royer, James S.; Sharma, Arun. Systems that learn: an introduction to learning theory (2nd). Bradford Book / MIT Press. 1999. ISBN 0-262-10077-0. LCCN 98-34861.
Lerman, Manuel. Degrees of unsolvability. Perspectives in Mathematical Logic. Springer-Verlag. 1983. ISBN 3-540-12155-2.
Nies, André. Computability and Randomness. Oxford University Press. 2009. ISBN 978-0-19-923076-1.
Odifreddi, Piergiorgio. Classical Recursion Theory. North-Holland. 1989. ISBN 0-444-87295-7.
Odifreddi, Piergiorgio. Classical Recursion Theory. II. Elsevier. 1999. ISBN 0-444-50205-X.

Sorğu sənədləri və kolleksiyalar

Enderton, Herbert Bruce. Elements of Recursion Theory // Barwise, Jon (redaktor). Handbook of Mathematical Logic. North-Holland. 1977. 527–566. ISBN 0-7204-2285-X.

Tədqiqat sənədləri və kolleksiyalar

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. JSTOR 2964290.
Gold, E. Mark. "Language Identification in the Limit" (PDF). Information and Control. 10 (5). 1967: 447–474. doi:10.1016/s0019-9958(67)91165-5. [1]
Jockusch, Carl Groos Jr. "Semirecursive sets and positive reducibility". Transactions of the American Mathematical Society. 137 (2). 1968: 420–436. doi:10.1090/S0002-9947-1968-0220595-7. JSTOR 1994957.
Kleene, Stephen Cole; Post, Emil Leon. "The upper semi-lattice of degrees of recursive unsolvability". Annals of Mathematics. Series 2. 59 (3). 1954: 379–407. doi:10.2307/1969708. JSTOR 1969708.
Myhill, John R. Sr. "The lattice of recursively enumerable sets". The Journal of Symbolic Logic. 21. 1956: 215–220. doi:10.1017/S002248120008525X.
Post, Emil Leon. "Recursive unsolvability of a problem of Thue". Journal of Symbolic Logic. 12 (1). 1947: 1–11. doi:10.2307/2267170. JSTOR 2267170. Reprinted in Davis, 1965.

Xarici keçidlər

[Feferman_1990-1] 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. ISBN 978-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).)

[Soare_2011-2] Soare, Robert Irving. "Computability Theory and Applications: The Art of Classical Computability" (PDF). Department of Mathematics. University of Chicago. 2011-12-22. 2022-06-30 tarixində arxivləşdirilib (PDF). İstifadə tarixi: 2017-08-23.

[Friedman_1998-3] Friedman, Harvey. "Renaming recursion theory". FOM email list. 1998-08-28. 2022-03-01 tarixində arxivləşdirilib. İstifadə tarixi: 2006-01-09.

[Rado_1962-4] Radó, Tibor. "On non-computable functions". Bell System Technical Journal. 41 (3). May 1962: 877–884. doi:10.1002/j.1538-7305.1962.tb00480.x.

[Kleene_1952-5] Kleene, Stephen Cole. Introduction to Metamathematics. North-Holland. 1952. 300, 376. ISBN 0-7204-2103-9.

[Simpson_1998-6] Simpson, Stephen George. "What is computability theory?". FOM email list. 1998-08-24. 2021-12-18 tarixində arxivləşdirilib. İstifadə tarixi: 2006-01-09.

[Fortnow_2004-7] Fortnow, Lance Jeremy. "Is it Recursive, Computable or Decidable?". 2004-02-15. 2022-08-07 tarixində arxivləşdirilib. İstifadə tarixi: 2018-03-22.

[1]

[2]

[3]

[4]

[5]

[6]

[7]