2.1. Исполнитель

Прежде чем давать формальное определение алгоритма, введем в обсуждение неформальный персонаж - Исполнителя. Это довольно ограниченное существо - у него конечная память (размер которой, впрочем, может быть сколь угодно велик). Доступные Исполнителю действия также весьма просты. Исполнитель умеет различать символы некоторого конечного алфавита (сколь угодно большого) и правильно их записывать. Кроме того, он умеет пользоваться таблицами. Это означает, что если выдать ему книжку, в которой приведена таблица некоторой функции из конечного множества в конечное множество, то Исполнитель может находить по аргументам функции ее значение.

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

Инструкции, которым следует Исполнитель, собраны в отдельную книжечку. Можно считать, что они задают таблицу значений функции

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

С другой стороны, данное выше описание уже легко превратить в формальное определение, что и будет сделано в следующем подразделе. Впрочем, подробности этого формального определения не так уж важны. Единственное существенное в дальнейшем свойство состоит в том, что утверждение "Исполнитель правильно выполнил очередной шаг вычислений" можно записать достаточно короткой логической формулой, переменные которой кодируют описание состояний нашей системы (Исполнитель, тетрадь, книжка с инструкциями) до и после очередного действия Исполнителя. Это свойство хорошо согласуется с неформальным представлением об элементарном действии - если сделано какое-то простое действие, то и утверждение о том, что сделано именно это действие, должно быть не слишком сложным (длинным). Доказательство этого свойства для используемого ниже формального определения алгоритма легко извлечь из приведенного в разд. 5 наброска доказательства теоремы Кука-Левина.