Понятие алгоритма и его уточнения

понятие алгоритма дается в следующей форме: "Под алгоритмом понимают понятное и точное предписание исполнителю совершить последовательность действий, направленных на решение поставленной задачи". Понятие алгоритма является одним из основных понятий современной математики и является объектом исследования специального раздела математики - теории алгоритмов.Точное математическое определение понятия "алгоритм" было выработано лишь в тридцатых годах XX века. Почему же до этого времени математики довольствовались интуитивным понятием алгоритма? Это связано с тем, что обычно понятие алгоритма встречалось в связи с конкретным решением задачи. Об алгоритме говорили лишь тогда, когда предлагался способ решения какого-либо класса задач. В начале XX века в математике накопилось большое количество задач, которые не поддавались решению, несмотря на то, что над ними думали первоклассные ученые. Возникло подозрение, что для некоторых из этих задач вообще не существует разрешающего алгоритма. Утверждение о неразрешимости того или иного класса задач можно было вывести, только имея точное определение алгоритма, надо было знать, несуществование чего требуется доказать. Попытки дать строгое математическое определение алгоритма, согласующееся с интуитивным представлением об алгоритме, привели к выработке сразу нескольких определений (Черч, Пост, Тьюринг, Марков и др.). Впоследствии выяснилось, что все эти определения равносильны между собой и, следовательно, определяют одно и то же понятие.В качестве основы для уточнения понятия алгоритма мы выбираем так называемые машины с неограниченными регистрами, или, короче, МНР [4]. Изложение на базе МНР привлекательно ввиду близости этих машин к реальным ЭВМ.

Каждый алгоритм имеет дело с данными - входными, промежуточными и выходными. Поскольку мы собираемся уточнять понятие алгоритма, нужно уточнить и понятие данных. В качестве данных для МНР мы ограничиваемся множеством Z0 неотрицательных целых чисел. Такое ограничение не является существенным, поскольку другие виды объектов и операции над ними могут быть закодированы натуральными числами и представлены как операции над натуральными числами.