Алгоритм (Кузнецов)
АЛГОРИТМ (от algorismus — латинизированное имя среднеазиатского ученого IX в. аль-Хорезми) — четко заданная конечная последовательность процедур, приводящая к решению любой конкретной задачи из некоторого класса задач. Построение А. для задач определенного типа, т.е. алгоритмизация их решения, сводит поиск ответа на поставлен ный вопрос к столь простым операциям, что они могут выполняться чисто механически, а потому могут быть переданы некому устройству (например, компьютеру), которое и осуществит поиск ответа в соответствии с предписанием А.
Поиск А. для решения различного рода задач всегда был важной темой исследований в математике. Начиная со средневековья хорошо известны и вошли в школьный курс арифметики А. сложения, вычитания, умножения и деления «столбиком» в десятичной системе счисления, А. нахождения наибольшего общего делителя, А. нахождения корней квадратных уравнений и многое другое. Развитие современной логики привело к необходимости нахождения А. для решения многих задач данной науки. Так, распознавание логических законов в логике высказываний решается с помощью А. построения таблиц истинности. В настоящее время большое внимание уделяется нахождению удобных А. поиска доказательства теорем для различных логических теорий.
Однако многие проблемы математики и логики в течение длительного времени не поддавались алгоритмизации. Возникли подозрения, что для них вообще нельзя построить А. Для доказательства такого рода отрицательной теоремы (о несуществовании А.) необходимо было исходное интуитивное понятие А. уточнить строго формальным образом. Эта работа была выполнена в 30 -50-е гг. XX в. и привела к нескольким эквивалентным друг другу уточнениям понятия А. Такими уточнениями являются понятия абс-трактной машины Тьюринга, общерекурсивной функции, Л-определимой функции, нормального алгоритма Маркова и ряд других. На основе этих уточнений были получены результаты о несуществовании А. для многих задач логики и математики. В частности, А. Черчем была доказана теорема о несу-ществовании А., который по любой формуле первопорядковой логики предикатов устанавливал бы, является ли она законом этой логической теории или нет.
В современной науке теория А. является основой конструктивного направления в математике и логике. Она является также базовой дисциплиной в области вычислительной техники и программирования, машинного решения самых разнообразных задач, моде-лирования различных процессов.
Словарь философских терминов. Научная редакция профессора В.Г. Кузнецова. М., ИНФРА-М, 2007, с. 7-8.