Алгоритм

АЛГОРИТМ [от algorithmi; algorismus, первоначально — латинская транслитерация имени среднеазиатского учёного 9 века Хорезми (Мухаммед бен Муса аль-Хорезми)], программа, определяющая способ поведения (вычисления); система правил (предписаний) для эффективного решения задач. При этом подразумевается, что исходные данные задач могут изменяться в определенных пределах (массовость алгоритмов); процесс применения правил к исходным данным (путь решения задачи) определён однозначно (детерминированность алгоритма); на каждом шаге процесса (применения правила) известно, что считать его результатом (результативность алгоритма). Свойство массовости алгоритмов означает, что алгоритм связан с решением общей проблемы, в условия которой входят параметры; ответ «да» или «нет» на эту проблему даётся не прямо, а косвенно — в зависимости от значений параметров, в общем случае допускающих счётно-бесконечное множество значений. Поэтому точное описание алгоритма предполагает указание на множество возможных значений параметров (т. е. частных вопросов) проблемы. Обычно (без ущерба для общности понятия алгоритма) в качестве возможных значений параметров выбирают слова в некотором фиксированном алфавите, при этом алгоритм сводится к процессу преобразования слов. Результативность процесса применения алгоритма связывают с его остановкой (обрывом), что рассматривают как применимость алгоритма к исходным данным задачи. Свойство детерминированности алгоритма выражается в том, что когда заданы алгоритмы и значения параметров (т. е. выбран частный случай проблемы), процесс решения идёт чисто формально (механически), так что во всех деталях известны последовательность и содержание конкретных (дискретных) шагов работы алгоритма. Детерминированность исключает возможность произвольных решений, что достигается изоляцией алгоритмического процесса от воздействий извне. Именно эта черта алгоритма делает его одновременно и синонимом автоматически работающей машины, и основой автоматизации процессов преобразования информации.

Общая проблема совместно с требованием разыскания алгоритма называется алгоритмической. Если алгоритм предложен, то спрашивается: всегда ли ответы по предложенному алгоритму будут ответами на частные вопросы данной алгоритмической проблемы? Это выясняют доказательством соответствия алгоритма данной проблеме, после чего алгоритмическую проблему считают разрешимой алгоритмом (или алгоритмически разрешимой). Обычно задачи, решаемые алгоритмом, сводятся к распознаванию свойств конструктивных объектов (см. Конструктивное направление). Например, алгоритм распознавания свойства общезначимости для формул логики высказываний даётся их табличной оценкой. Это же свойство характеризует и множество доказуемых формул исчисления высказываний, которое таким образом, алгоритмически разрешимо относительно истинности.

Вопрос о проблемах, разрешимых алгоритм, связан с вопросом об использовании машин вместо человека и пределах автоматизации процессов мышления. Вера в алгоритмическую разрешимость всех (по крайней мере, всех математических и логических) проблем имела значительное влияние в философии начиная с Декарта и Лейбница. В 1931 году К. Гёдель доказал, что в системах аксиом определенного вида есть проблемы, неразрешимые алгоритмом этих систем, в связи с чем возник вопрос об описании класса всех возможных типов алгоритмов в рамках строгой (формальной) теории алгоритма. В 1936 году появилось несколько вариантов стандартных систем уточнения понятия алгоритма (формализации функций, вычислимых по Гёделю, Клини, Тьюрингу, Черчу) и была высказана эмпирически обоснованная гипотеза, что иных алгоритмов, удовлетворяющих свойствам содержательного понятия алгоритма, но неэквивалентных стандартным формализациям, не существует. Эта гипотеза означала признание принципиальной завершённости поиска средств, привлекаемых для решения алгоритмических проблем, и вместе с тем — признание существования алгоритмически «абсолютно неразрешимых» проблем. Однако подобные выводы отнюдь не ограничивали развитие самой теории алгоритмов, ставшей с начала 50-х годов внутри логики и математики теоретической основой конструктивизма, а в области вычислительной науки и техники — основой машинного решения математических задач, моделирования сложных процессов и автоматизации процессов производства. Важный этап этого развития — созданная А. А. Марковым теория нормальных алгоритмов, уточняющая непосредственно интуитивное понятие алгоритма, и предложенная им формулировка основных абстракций теории алгоритмов.

M. M. Новосёлов.

Философский энциклопедический словарь. — М.: Советская энциклопедия. Гл. редакция: Л. Ф. Ильичёв, П. Н. Федосеев, С. М. Ковалёв, В. Г. Панов. 1983.

Литература:

Колмогоров А. Н., Успенский В. А., К определению А., «Успехи математических наук», 1958, т. 13, в. 4 (82); Трахтенброт Б. А., А. и машинное решение задач, М., 1960; Mальцев А. И., Алгоритм и рекурсивные функции, М., 1965; Роджерс X., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972; Бирюков Б. В., Алгоритмический подход к науке и концепция расплывчатых алгоритмов, в кн.: Кибернетика и совр. науч. познание, M., 197B; Криницкий Н. А., Алгоритм вокруг нас, М., 1977; Успенский В. А., Машина Поста, М., 1979.