16.Алгоритмы и вычислимые функции

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

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

Таким образом, алгоритм - это процедура U, которая:

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

2) Расчленена на отдельные простые шаги; каждый шаг состоит в непосредственной обработке возникшего к этому шагу состояния S в состояние S* =омега (подкова) с индексом u (S).

3) Непосредственная переработка S в состояние S* =омега (подкова) с индексом u (S) производится однозначно заданным способом лишь на основании информации о виде заранее ограниченной «активной» части состояния S и затрагивает лишь эту активную часть.

4) Процесс переработки Ао = А в A1 = омега u (Ao), A1 в А2 = омега u (A1), А2 в Аз = омега u (А2) и т.д. продолжается до тех пор, пока либо не произойдет безрезультатная остановка (или оператор омега u не определен для возникшего состояния), либо не появится сигнал о получении «решения». При этом не исключается возможность непрекращающегося процесса переработки.

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