Algorithms are the essence of Informatics and of some classical parts of Mathematics too. But until the 1930s algorithms were considered only as a tool for solving important for science and practice tasks. Since the term is not formal, only from this moment the algorithms are an object of study that raised a number of important issues. For example, can the concept of algorithm be formalized? What tasks can be solved algorithmically and are there any tasks that cannot be solved with an algorithm? Why do different algorithms for the same task work for a significantly different time? Therefore, we can safely say that the foundations of the Mathematical Theory of Algorithms (which is the subject of this article) were laid in the 1930s. The year 2021 marks the 50th anniversary of the publication of a very important result of the theory and the exposition in this article focuses on this result and the following challenge that has not received an answer yet.
Алгоритмите са същността на информатиката, както и на някои класически дялове на математиката. Но до 1930-те години алгоритмите се разглеждат само като инструмент за решаване на важни за науката и практиката задачи. Тъй като понятието не е формално, едва откъм средата на 1930-те години на тях започва да се гледа като на обект за изследване и да се поставят редица съществени въпроси. Например, може ли понятието алгоритъм да се формализира? Какви задачи могат да се решават алгоритмично и има ли задачи, които не могат да се решат с алгоритъм? Защо различните алгоритми за една и съща задача работят за съществено различно време? Затова можем смело да кажем, че през 30-те години на миналия век се поставят основите на Математическата теория на алгоритмите, която е предмет на настоящата статия. През 2021 г. се навършват 50 години от публикуването на много важен резултат на тази теория. Изложението в статията е съсредоточено върху този резултат и последвалото от него предизвикателство, което не е получило още отговор.
