Математическая энциклопедия - алгоритмов теория

раздел математики, изучающий общие свойства алгоритмов. Содержательные явления, приведшие к образованию понятия "алгоритм", прослеживаются в математике в течение всего времени ее существования. Однако само это понятие сформировалось лишь в 20 в. и стало предметом самостоятельного изучения (по-видимому, впервые, хотя еще в расплывчатом виде) в 20-х гг.

20 в. в трудах представителей интушионизма Л. Э. Я. Брауэра (L. Е. J. Brouwer) и Г. Вейля (Н. Weyl, см. [1]). Началом сиотематич. разработки А. т. можно считать 1936, когда А. Чёрч (A. Church, [2]) опубликовал первое уточнение понятия вычислимой функции (предложив отождествлять понятие всюду определенной вычислимой функции, имеющей натуральные аргументы и значения, с понятием общерекурсивной функции) и привел первый пример функции, не являющейся вычислимой, а А.

В дальнейшем А. т. получила развитие в трудах С. К. Клини (S. С. Kleene), Э. .