Интуитивное понятие алгоритма и его уточнение

Мухаммед ибн Муса ал-Хорезми (IX в) в своем арифметическом трактате изложил основы индийской системы счисления и искусство счета в ней. Латинский перевод трактата, относящийся к XII в начинается словами «Dixit algorizmi» — «Сказал аль-Хорезми». С тех пор термин «алгоритм» стал применяться для обозначения первых алгоритмов цифровых вычислений, затем и для произвольных алгоритмов.

Интуитивное понятие алгоритма – одно из основных понятий математики, не допускающее определения в терминах более простых понятий.

Пусть задано бесконечное множество задач и указано, что понимается под решением каждой из них. Говорят, что существует алгоритм для решения данного бесконечного множества задач, если существует единый способ, позволяющий, для любой задачи этого множества, в конечное число шагов, найти ее решение.

Это не является определением, т.к. выражение «единый», «конечное число шагов» лишены математической точности.

Черты, характерные для интуитивного понятия алгоритма

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

Конструктивный объект – тот, который может быть набран весь целиком и представлен для рассмотрения.

Примерами конструктивных объектов являются булевы функции, формулы алгебры логики, натуральные и рациональные числа, матрицы с натуральными или рациональными элементами, многочлены от неизвестных с рациональными коэффициентами.

Неконструктивными объектами являются, например, любые действительные числа, представления которых в десятичной записи a₀ a₁…a_n… ни для какого nиз натуральных чисел не может быть целиком представлено для рассмотрения. Числа и не являются конструктивными объектами.

Понятно, что понятие алгоритма, описываемое свойствами 1-6, является нестрогим: в формулировке этих свойств встречаются слова, не имеющие точного математического определения. Необходимо также отметить, что, вообще говоря, не предполагается, что процесс применения алгоритма к исходным данным обязательно должен закончиться результатом через конечное число шагов. Процесс может закончиться безрезультатно или не закончиться вообще. В этом случае говорят, что алгоритм неприменим к рассматриваемым исходным данным.

Примеры алгоритмов:

Алгоритмы арифметических действий с числами в двоичной системе счисления
алгоритм нахождения НОД 2-х целых чисел, 2-х многочленов от переменной х;
алгоритм извлечения ?n,?n?N ;
алгоритм дифференцирования многочлена от переменной ;
алгоритм нахождения определителя квадратной матрицы А над ?;

Вплоть до 30-х годов двадцатого столетия понятие алгоритма оставалось интуитивно понятным, имевшем скорее методологическое, а не математическое значение. Так, к началу ХХ в. много ярких примеров дала алгебра и теория чисел. Среди них упомянем алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел или двух целочисленных многочленов, алгоритм Гаусса решения системы линейных уравнений над полем, алгоритм нахождения рациональных корней многочленов одного переменного с рациональными коэффициентами, алгоритм Штурма определения числа действительных корней многочлена с действительными коэффициентами на некотором отрезке действительных чисел, алгоритм разложения многочлена одного переменного над конечным полем на неприводимые множители. Указанные алгоритмические проблемы решены путем указания конкретных разрешающих процедур. Для получения результатов такого типа достаточно интуитивного понятия алгоритма.

Но тогда же были выдвинуты алгоритмические проблемы, для которых не удавалось построить алгоритм, да и само существование таких алгоритмов было под сомнением.

Примеры:

10-я проблема Гильберта о разрешимости произвольного диофантового уравнения;
Проблема определения общезначимости произвольной формулы логики предикатов.

Указанные проблемы были решены отрицательно, т.е. доказано, что не существует алгоритма для их решения (соответственно Ю. Матиясевич (1970 г.) и А. Черч (1936г.)).

Для доказательства несуществования алгоритма, интуитивного понятия алгоритма недостаточно. Оно должно быть уточнено и формализовано. С этой целью построены несколько формальных алгоритмических моделей, представляющих алгоритм как:

вычисление функции натурального аргумента (частично-рекурсивные функции);
работу некоторой абстрактной машины (машины Тьюринга, машина с неограниченными регистрами);
последовательные преобразования слов, записанных в произвольном алфавите (нормальные алгоритмы Маркова).

Для теории сложности вычислений, выбор модели, в которой конструируются алгоритмы, не имеет принципиального значения. Существуют способы реализации одних алгоритмических моделей с помощью других. При этом сохраняется принадлежность алгоритмов определенному классу сложности (P, N и др.).

Алгоритм, записанный в виде программы на языке программирования высокого уровня, также может быть смоделирован с помощью одной из упомянутых формальных моделей.