Основные требования к алгоритмам.

1. Каждый алгоритм имеет дело с данными - входными, промежуточными, выходными. Для того, чтобы уточнить понятие данных, фиксируется конечный алфавит исходных символов (цифры, буквы и т.п.) и указываются правила построения алгоритмических объектов. Типичным используемым средством является индуктивное построение. Например, определение идентификатора в АЛГОЛЕ: идентификатор - это либо буква, либо идентификатор, к которому справа приписана либо буква, либо цифра. Слова конечной длины в конечных алфавитах - наиболее обычный тип алгоритмических данных, а число символов в слове - естественная мера объема данных.

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

3. Алгоритм состоит из отдельных элементарных шагов, причем множество различных шагов, из которых составлен алгоритм, конечно. Типичный пример множества элементарных шагов - система команд ЭВМ.

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

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

6. Алгоритм предполагает наличие механизма реализации алгоритма, который по описанию алгоритма порождает процесс реализации на основе исходных данных.

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

Данная модель была предложена в 30-х годах А.Тьюрингом и оказала влияние на разработку ЭВМ. В данном подходе “алгоритм” - это программа некоторой конкретной ЭВМ, а функция алгоритмически вычислима, если можно запрограммировать ее вычисление.