АЛГОРИТМОВ ТЕОРИЯ

АЛГОРИТМОВ ТЕОРИЯ — раздел математики, изучающий общие свойства алгоритмов. А. т. начала оформляться в 20—30-х гг. XX в. Началом систематической разработки А. т., видимо, следует считать 1936 г., когда американский математик А. Чёрч опубликовал определение вычислимой функции , предложив отождествить понятие определенной на множестве всех натуральных чисел вычислимой функции с понятием общерекурсивной функции и привел первый пример функции, не являющейся вычислимой. Тем самым был подготовлен фундамент для строгого определения понятия алгоритма, что и было сделано независимо друг от друга американским математиком Э. Л. Постом и английским математиком А. М, Тьюрингом. Оба дали определение алгоритма в терминах абстрактных идеализированных машин, получивших в дальнейшем название Тьюринга машина.

Э. Л. Постом был выдвинут принцип о том, что любой конкретный алгоритм описывается в терминах данного им определения. Дальнейшее развитие получила А. т. в работах американского математика С. К. Клини и советских математиков А. А. Маркова и А. Н. Колмогорова. А. А. Марков дал новое определение алгоритма с помощью введенного им понятия нормального алгоритма. Наиболее общее определение алгоритма предложил А. Н. Колмогоров. Впрочем, все определения, как оказалось впоследствии, эквивалентны друг другу.

На основе А. т. была доказана алгоритмическая неразрешимость (отсутствие алгоритма) для ряда задач. Первые результаты этого рода принадлежат Э. Л. Посту и А. А. Маркову (алгоритмическая неразрешимость тождества слов для полугрупп).