50 години от публикуването на Теоремата на Кук
Абстракт
Алгоритмите са същността на информатиката, както и на някои класически дялове на математиката. Но до 1930-те години алгоритмите се разглеждат само като инструмент за решаване на важни за науката и практиката задачи. Тъй като понятието не е формално, едва откъм средата на 1930-те години на тях започва да се гледа като на обект за изследване и да се поставят редица съществени въпроси. Например, може ли понятието алгоритъм да се формализира? Какви задачи могат да се решават алгоритмично и има ли задачи, които не могат да се решат с алгоритъм? Защо различните алгоритми за една и съща задача работят за съществено различно време? Затова можем смело да кажем, че през 30-те години на миналия век се поставят основите на Математическата теория на алгоритмите, която е предмет на настоящата статия. През 2021 г. се навършват 50 години от публикуването на много важен резултат на тази теория. Изложението в статията е съсредоточено върху този резултат и последвалото от него предизвикателство, което не е получило още отговор.
Литература (библиография)
N. Chomsky. Three models for the description of language. IRE Transactions on Information Theory, 2 (1956), 113–124.
A. Church. An unsolvable problem of elementary number theory. American Journal of Mathematics, 58 (1936), 345–363.
S. A. Cook. The complexity of theorem proving procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing, 1971, 151–158, doi:10.1145/800157.805047.
M. R. Garey, D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness (ed. W. H. Freeman), 1979, ISBN 0-7167-1045-5.
S. C. Kleene. λ-definability and recursiveness. Duke Mathematical Journal, 2, No 2 (1936), 340–352, doi:10.1215/s0012-7094-36-00227-2.
E. Post. Finite Combinatory Processes – Formulation 1. Journal of Symbolic Logic, 1 (1936), 103–105.
A. M. Turing. On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42 (1936), 230–265. DOI:10.1112/plms/s2-42.1.230.
L. A. Levin. Universal'nyye zadachi perebora. Problemy peredachi informatsii, 9, No 3 (1973), 115–116.
A. A. Markov. Teoriya algorifmov. Moskva, Izd. AN SSSR, 1954.