АЛГОРИТМОВ ТЕОРИЯ
— раздел математики, в котором изучаются теоретические возможности эффективных процедур вычисления (алгоритмов) и их приложения. Осн. понятие теории — понятие алгоритма — в интуитивном понимании существует в математике. Довольно давно. Под алгоритмом понимают точное предписание для совершения некоторой последовательности элементарных действий над исходными данными любой задачи из некоторого класса (вообще бесконечного) однотипных задач, в результате выполнения которой получится решение этой задачи. Примером алгоритма может служить правило нахождения наибольшего общего делителя двух чисел (алгоритм Евклида). Формула для нахождения корней квадратного уравнения также является своеобразной формой записи алгоритма. Она указывает, какие арифм. действия и в какой последовательности нужно производить над коэфф. квадратного уравнения, чтобы получить корни этого уравнения. А. т. является в настоящее время важным и быстро развивающимся разделом логики математической. Интерес к ней объясняется, с одной стороны, внутр. интересами самой математики (вопросы оснований математики, конструктивное и интуиционистское направления в математике, алгоритм, проблемы алгебры и т. п.), а, с другой, — бурным развитием электронной вычислительной техники и теор. кибернетики. Практические и теор. вопросы реализации алгоритмов на современных вычислительных машинах являются содержанием такого важного раздела теор. кибернетики, как программирование.
Точные матем. понятия, которые в том или ином смысле формализовали интуитивное понятие алгоритма, предложены только в середине 30-х гг. 20 в. То, что было предложено несколько различных уточнений, объясняется в какой-то мере разнообразием тех (конструктивных) объектов, над которыми осмыслено понятие эффективного (алгоритмического) преобразования. Такими объектами могут быть натуральные числа, конечные последовательности натуральных чисел (кортежи), слова в некотором конечном алфавите, матрицы, конечные графы и т. п.
Исторически первые из предложенных понятий можно разделить на два вида.
1. Описывается некоторый класс арифм. ф-ций (вообще говоря, частичных), т. е. функций от конечного числа натуральных аргументов с натуральными значениями. Эти ф-ции обладают некоторыми эффективными процедурами нахождения значения ф-ции (если оно существует) по заданным значениям аргументов. Ф-ции из этого класса наз. частично рекурсивными (ч. р. ф.), а в случае, если ч. р. ф. всюду определены, их наз. общерекурсивными (о. р. ф.). Класс ч. р. ф. определили Ж. Эрбран, К. Гедель и С.-К. Клини, исходя из исследований формализованной арифметики с помощью подходящих функциональных исчислений. Независимое определение этого класса ф-ций дал А. Черч с помощью т. н. исчисления 
-конверсий. Класс всех ч. р. ф. и предлагается в качестве определения для класса всех арифметических алгоритмически вычислимых ф-ций (см. Черча тезис).
2. Описываются точные матем. понятия машины и вычислимости на машине. Такие понятия машины и вычислимости на машине предложили независимо один от другого
3. Пост и А. Тьюринг. Эти «теоретические вычислительные машины» обычно наз. Тьюринга машинами. Оказалось, что класс арифм. ф-ций, для которых существует машина Тьюринга, вычисляющая по значениям аргументов значение ф-ций (если оно существует), совпадает с классом всех ч. р. ф. и наоборот, каждая ч. р. ф. вычислима на подходящей машине Тьюринга. В общих чертах различие между двумя рассмотренными выше видами определений можно сформулировать так: в первом дается точное описание класса вычислимых арифм. ф-ций, во втором — точное описание некоторого класса алгоритм, преобразований (вычислений на машине Тьюринга). Позднее были предложены и другие понятия, уточняющие понятие алгоритма, — канонические исчисления Э. Поста, нормальные алгорифмы, А. А. Маркова, алгоритмы А. Н. Колмогорова и т. д. Для всех этих уточнений оказалось, что вычислимыми арифм. ф-циями являются
4. р. ф. Таким образом, понятие эффективно вычислимой арифм. ф-ции можно считать вполне определенным. Однако еще не дано наиболее общее определение понятия алгоритм, вычислимости. Характерной особенностью почти всех уточнений понятия алгоритма является представление соответствующих понятий в виде тех или иных исчислений. Поэтому А. т. можно считать разделом матем. логики, где понятие исчисления — одно из основных.
Исследования по А. т. так же, как и приведенные выше определения, можно, естественно, разделить на два направления.
I. Исследования, в которых класс всех ч. р. ф. является либо осн. объектом исследования, либо осн. орудием исследования. Рассмотрим более подробно некоторые из разделов этого направления. 1) Исследование класса всех 
изучение подклассов этого класса — примитивно рекурсивных ф-ций, элементарных функций и т. п.; б) классификация ч. р. ф. с помощью иерархий; в) алгебр, изучение класса ч. р. ф. и о. р. ф. (см. Рекурсивные функции). 2) Введение с помощью ч. р. ф. новых естественных понятий и их изучение: а) определение (в терминах ч. р. ф.), изучение и классификация рекурсивных и рекурсивно перечислимых мн-в.
Понятия рекурсивного и рекурсивно перечислимого мн-в являются одними из осн. в своевременной А. т. Первое из них уточняет интуитивное понятие разрешимого мн-ва (т. е. мн-ва, для которого существует алгоритм, позволяющий по любому элементу определять, принадлежит Он к этому мн-ву или нет), а второе — понятие мн-ва, для которого существует алгоритм последовательного перечисления всех его элементов; б) сравнение и классификация алгоритм, природы произвольных подмножеств мн-ва натуральных чисел. Основой для такого сравнения служит понятие сводимости (то-сводимость, - сводимость, тьюрингова сводимость и др.) и соответствующее каждому понятию сводимости понятие степени сводимости. Понятия сводимости и ряд других понятий позволяют своеобразно классифицировать, располагать в иерархии большой класс подмножеств мн-ва натуральных чисел. 3) Обобщения и расширения понятий. Уже при определении некоторых сводимостей, напр., понятия тьюринговой сводимости, появляются относительные понятия, такие, как ф-ция, частично рекурсивная относительно мн-ва А, мн-во, рекурсивно перечислимое относительно А, и многие др. Понятия сводимости определяют уже не только для множеств, но и для классов множеств (и функций). Таким понятием является, напр., понятие массовой проблемы по Ю. Т. Медведеву. Для введения понятия сводимости массовых проблем используют понятие эффективного оператора. Предприняты попытки уточнить понятия вычислимости и для не конструктивных объектов, напр., определить понятие вычислимого функционала конечного типа, определенного на несчетном мн-ве функционалов низшего типа. Возможность использования результатов теории рекурсивных ф-ций для произвольных, не более чем счетных, множеств реализуется нумераций теорией. В теории нумераций естественным образом находят уточнение многие алгоритм, проблемы алгебры, и других разделов математики.
II. Исследования, в которых осн. упор делается на механизм вычисления. Существует ряд наиболее важных разделов А. т. этого направления исследований. 1) Теория конечных автоматов. Автоматы конечные являются наиболее изученным классом вычисл. устройств. Эта теория применяется, напр., при проектировании электронных вычислительных машин (ЭВМ). 2) Машины Тьюринга. Проводятся исследования возможностей таких машин в организации вычислений с теми или иными ограничениями, сравнивается работа машины с разнымчислом лент, изучаются возможности вычисления в реальное время и многое др. 3) Автоматы растущие. Это понятие возникло в основном в связи с попыткой дать наиболее общее определение алгоритм. вычисления, а также в связи с исследованиями Дж. фон Неймана по самовоспроизводящимся машинам. 4) Изучаются многие спец. виды других машин, связанные часто с обобщениями понятия вычислимости, напр., машины с «оракулом» и др.
Следует особо отметить проблему поиска понятия алгоритмов сложности, т. е. понятия, интуитивно достаточно хорошо воспринимаемого. Предложено несколько таких понятий. 1) Сложность алгоритма оценивается по тем или иным параметрам работы алгоритма (см. Сигнализирующая функция). Этот подход связан в основном со 2-м направлением исследований в А. т., т. е. эти понятия определяются в терминах работы конкретных вычисл. устройств (напр., машин Тьюринга). 2) Сложность алгоритма определяется через сложность его программы, записи (А. Н. Колмогоров, А. А. Марков). В определении используется введенное А. Н. Колмогоровым понятие сложности конечных слов. 3) Понятие сложности вводится не для отдельных алгоритмов, а для класса алгоритмов. Такое понятие сложности классов можно ввести с помощью понятий теории нумераций.
Результаты А. т. находят различные применения, начиная с использования результатов теории конечных автоматов в практике проектирования ЭВМ и кончая использованием рекурсивных функций в конструктивной математике. Существует и ряд других важнейших применений А. т. Первыми результатами А. т., имеющими большое принципиальное значение для всей математики, были Геделя теоремы о неполноте формализованной арифметики и теорема Черча об алгоритм, неразрешимости (о невозможности алгоритма) для проблемы разрешения узкого исчисления предикатов. Исчисление предикатов узкое является оси. исчислением современной матем. логики. Проблема разрешения для него состоит в том, чтобы построить алгоритм, позволяющий по любой формуле узкого исчисления предикатов эффективно определить, является ли эта формула доказуемой. Аналогичные проблемы разрешения возникают и для конкретных формализованных теорий (напр., теории групп, колец, арифметики и т. п.). Раздел матем. логики, который занимается изучением таких проблем разрешения, имеет название элементарные теории. Алгоритм, проблемы возникают и в алгебре (напр., проблема тождества слов для полугрупп и групп). Принципиальные результаты в этом направлении получили сов. математики (неразрешимость проблемы тождества слов для полугрупп доказал А. А. Марков, а неразрешимость проблемы тождества для групп — П. С. Новиков). Лит.: Марков А. А. Теория алгорифмов. «Труды Математического института им. В. А. Стеклова АН СССР», 1954, т. 42 [библиогр. с. 373—374]; Успенский В. А. Лекции о вычислимых функциях. М., 1960 [библиогр. с. 476-481 ]; Мальцев А. И. Алгоритмы и рекурсивные функции. М., 1965 [библиогр. с. 375—381]; Клини С. К. Математическая логика. Пер. с аигл. М., 1973 [библиогр. с. 451—465]; Davis М. Computability and unsolvability. New York - Toronto - London, 1958; Роджерс X. Теория рекурсивных функций и эффективная вычислимость. Пер. с англ. М., 1972 [библиогр. с. 587— 599]; Захаров Д. А. рекурсивные функции. Новосибирск, 1970 [библиогр. с. 201—204].
Ю. Л. Ершов.
