Само слово «А.» происходит от algorithmi, являющегося, в свою очередь, латинской транслитерацией арабского имени хорезмийского математика 9 в. аль-Хорезми . В средневековой Европе А. называется десятичная позиционная система счисления и искусство счёта в ней, поскольку именно благодаря латинскому переводу (12 в.) трактата аль-Хорезми Европа познакомилась с позиционной системой.
Строение алгоритмического процесса. Алгоритмический процесс есть процесс последовательного преобразования конструктивных объектов (к. о.), происходящий дискретными «шагами»; каждый шаг состоит в смене одного к. о. другим. Так, при применении А. Ã к слову baaba возникают последовательно baaba, abaaba, baabab и т. д. А при применении, скажем, А. вычитания столбиком к паре <307, 49> последовательно возникнут такие к. о.:
При этом в ряду сменяющих друг друга к. о. каждый последующий полностью определяется (в рамках данного А.) непосредственно предшествующим. При более строгом подходе предполагается также, что переход от каждого к. о. к непосредственно следующему достаточно «элементарен» — в том смысле, что происходящее за один шаг преобразование предыдущего к. о. в следующий носит локальный характер (преобразованию подвергается не весь к. о., а лишь некоторая, заранее ограниченная для данного А. его часть и само это преобразование определяется не всем предыдущим к. о., а лишь этой ограниченной частью).
Т. о., наряду с совокупностями возможных исходных данных и возможных результатов, для каждого А. имеется ещё совокупность промежуточных результатов (п. р.), представляющая собой ту рабочую среду, в которой развивается алгоритмический процесс. Для Ã все три совокупности совпадают, а для А. вычитания столбиком — нет: возможными исходными данными служат пары чисел, возможными результатами — числа (все в десятичной системе), а промежуточные результаты суть «трёхэтажные» записи вида
где q — есть запись числа в десятичной системе, r — такая запись или пустое слово, а р — запись числа в десятичной системе с допущением точек над некоторыми цифрами.
Работа А. начинается подготовительным шагом, на котором возможное исходное данное преобразуется в начальный член ряда сменяющих друг друга промежуточных результатов; это преобразование происходит на основе специального, входящего в состав рассматриваемого А. «правила начала». Это правило для Ã состоит в применении тождественного преобразования, а для А. вычитания — в замене пары<а, b> на запись
Затем применяется «правило непосредственной переработки», осуществляющее последовательные преобразования каждого возникающего промежуточного результата в следующий. Эти преобразования происходят до тех пор, пока некоторое испытание, которому подвергаются все промежуточные результаты по мере их возникновения, не покажет, что данный промежуточный результат является заключительным; это испытание производится на основе специального «правила окончания». Например, для Ã правило окончания состоит в проверке, не начинается ли промежуточный результат на aa. (Если ни для какого из возникающих промежуточных результатов правило окончания не даёт сигнала остановки, то либо к каждому из возникающих промежуточных результатов применимо правило непосредственной переработки, и алгоритмический процесс продолжается неограниченно, либо же к некоторому промежуточному результату правило непосредственной переработки оказывается неприменимым, и процесс оканчивается безрезультатно.) Наконец, из заключительного промежуточного результата — также на основе специального правила — извлекается окончательный результат; для Ã это извлечение состоит в отбрасывании первых двух букв а, а для А. вычитания — в отбрасывании всего, кроме самой нижней строчки цифр. (Во многих важных случаях правило начала и правило извлечения результата задают тождественные преобразования и потому отдельно не формулируются.) Т. о., для каждого А. можно выделить 7 характеризующих его (не независимых!) параметров: 1) совокупность возможных исходных данных, 2) совокупность возможных результатов, 3) совокупность промежуточных результатов, 4) правило начала, 5) правило непосредственной переработки, 6) правило окончания, 7) правило извлечения результата.
«Уточнения» понятия А. Возможны дальнейшие «уточнения» понятия А., приводящие, строго говоря, к известному сужению этого понятия. Каждое такое уточнение состоит в том, что для каждого из указанных 7 параметров А. точно описывается некоторый класс, в пределах которого этот параметр может меняться. Выбор этих классов и отличает одно уточнение от другого. Во многих уточнениях все классы, кроме двух — класса совокупностей промежуточных результатов и класса правил непосредственной переработки, — выбираются единичными, т. е. все параметры, кроме указанных двух, жестко фиксируются. Поскольку 7 параметров однозначно определяют некоторый А., то выбор 7 классов изменения этих параметров определяет некоторый класс А. Однако такой выбор может претендовать на название «уточнения», лишь если имеется убеждение, что для произвольного А., имеющего допускаемые данным выбором совокупности возможных исходных данных и возможных результатов, может быть указан равносильный ему А. из определённого данным выбором класса А. Это убеждение формулируется для каждого уточнения в виде основной гипотезы, которая — при современном уровне наших представлений — не может быть предметом математического доказательства.
Первые уточнения описанного типа предложили в 1936 американский математик Э. Л. Пост и английский математик А. М. Тьюринг (см. Тьюринга машина ). Известны также уточнения, сформулированные советскими математиками А. А. Марковым (см. Нормальный алгоритм ) и А. Н. Колмогоровым (последний предложил трактовать конструктивные объекты как топологические комплексы определённого вида, что дало возможность уточнить свойство «локальности» преобразования). Для каждого из предложенных уточнений соответствующая основная гипотеза хорошо согласуется с практикой. В пользу этой гипотезы говорит и то, что, как можно доказать, все предложенные уточнения в некотором естественном смысле эквивалентны друг другу.
В качестве примера приведём (в модернизированном виде) уточнение, предложенное Тьюрингом. Чтобы задать тьюрингов А., надо указать: а) попарно непересекающиеся алфавиты Б, Д, Ч с выделенной в Д буквой l и выделенными в Ч буквами a и w, б) набор пар вида < рx, hTq >, где р, qÎЧ, x, hÎБÈД, а Т есть один из знаков —, 0, +, причём предполагается, что в этом наборе (называемой программой) нет 2 пар с одинаковыми первыми членами. Параметры А. задаются так: возможными исходными данными и возможными результатами служат слова в Б, а промежуточными результатами — слова в БÈДÈЧ, содержащие не более одной буквы из Ч. Правило начала: исходное слово Р переводится в слово laРl. Правило окончания: заключительным является промежуточный результат, содержащий w. Правило извлечения результата: результатом объявляется цепочка всех тех букв заключительного промежуточного результата, которая идёт вслед за w. и предшествует первой букве, не принадлежащей Б. Правило непосредственной переработки, переводящее А в А', состоит в следующем. Приписываем к А слева и справа букву l; затем в образовавшемся слове часть вида erx, где рÎЧ, заменяем на слово Q по следующему правилу: в программе ищется пара с первым членом рx; пусть второй член этой пары есть hTq; если Т есть - , то Q = qeh, ЕСли Т есть 0, то Q =eqh; если Т есть +, то О = ehq. Возникающее после этой замены слово и есть А'.