Уточнение понятия алгоритма

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

Каждый алгоритм служит для решения некоторого класса задач. Задачи должны быть записаны на некотором языке. Результат применения алгоритма – решение задачи– также должен быть записан на вполне определенном языке. Таким образом, в процессе выполнения алгоритма текст задачи преобразуется в текст ее решения. Процесс алгоритмического решения задачи должен быть дискретным. Он распадается на элементарные шаги и представляет собой цепочку преобразований вида

T₀ → T₁ → … → T_k,

где T₀ – текст, представляющий задачу, а T_k – текст, дающий ее решение. Преобразование текста на каждом шаге производится по предписаниям, которые берутся из конечного и фиксированного раз и навсегда списка. Как было показано в п. 4.2, тексты (слова над конечным алфавитом) могут быть занумерованы. При этом цепочка текстов «задача – решение» превратится в числовую цепочку их номеров:

n₀ → n₁ → … → n_k.

Мы получаем числовую функцию y=f(x), n₀→n_k, определенную на множестве номеров задач X⊂Nи принимающую значения в N. Алгоритм описывает не только саму функцию f(x), но и способ ее пошагового вычисления.

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

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

Применительно к упомянутым уточнениям понятия алгоритма принимается следующая гипотеза.

Тезис Черча. Числовая функция тогда и только тогда алгоритмически вычислима, когда она рекурсивна (или, что равносильно, вычислима по Тьюрингу, по Посту или по Маркову).