Формализация понятия алгоритма

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

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

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

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

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

Варианты словесного определения алгоритма принадлежат российским ученым А.Н. Колмогорову и А.А. Маркову.

Определение Колмогорова: Алгоритм – это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.

Определение Маркова: Алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.

Удивительным научным результатом является доказательство эквивалентности всех этих и нескольких других формальных определений алгоритма. Эквивалентность двух абстрактных моделей алгоритма состоит в том, что любой класс проблем, которые можно решить с помощью моделей одного типа, можно решить и на моделях другого типа (фактически в рамках одной модели можно выразить другие). Оказалось, что все алгоритмы в точном смысле для этих формальных моделей являются алгоритмами в интуитивном смысле, и все известные алгоритмы могут быть представлены алгоритмами в точном смысле (в рамках этих формализмов).

На основании этих результатов в информатике получило признание следующее положение: «Любое разумное определение алгоритма, которое может быть предложено в будущем, окажется эквивалентным уже известным определениям», что означает, по сути, предположение об адекватности понятий алгоритма в интуитивном смысле и алгоритма в точном смысле в одном из перечисленных эквивалентных формализмов. Это положение в настоящее время широко используется в качестве гипотезы, обоснованной в силу того, что не удалось найти противоречащих ей примеров. Эту гипотезу, однако, невозможно доказать строго, поскольку понятие алгоритма в интуитивном смысле является неформальным.

Исторически Алонзо Черч первый предложил отождествить интуитивное понятие алгоритма с одним из эквивалентных между собой точных определений. Алан Тьюринг независимо высказал предположение, что любой алгоритм в интуитивном смысле может быть представлен машиной Тьюринга (а значит, и в любой другой эквивалентной форме). Это предположение известно как тезис Черча-Тьюринга. Тезис Черча-Тьюринга просто отражает нашу уверенность в том, что разработанные формальные модели алгоритма достаточно полно представляют наше интуитивное его понимание.

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

Определение машины Тьюринга среди других эквивалентных определений кажется наиболее удобным для формального определения понятия алгоритма.

Отметим, что различные определения алгоритма, в явной или неявной форме, постулируют следующий ряд требований:

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

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

- алгоритм должен быть единым для всех допустимых исходных данных, т.е. удовлетворять требованию универсальности;

- алгоритм должен приводить к правильному по отношению к поставленной задаче решению, т.е. удовлетворять требованию правильности.