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

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

Поиск теоретических моделей происходил в трех направлениях, которые и определили три основных класса математических конструкций.

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

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

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

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

Рассмотрим более подробно эти математические конструкции.