Понятие об алгоритме и теории алгоритмов

 

Интуитивно под алгоритмом понимается процесс последовательного решения задачи, протекающей в дискретном времени так, что в каждый следующий момент времени система объектов алгоритма получается по определённому закону из системы объектов, имевшихся в предыдущий момент времени [19]. Интуитивно потому, что, строго говоря, понятие алгоритма сродни понятию множества, которое неопределимо.

В соответствии с ГОСТ 19781-74 «Машины вычислительные. Программное обеспечение. Термины и определения» алгоритм – это точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату. При этом предполагается наличие исполнителя алгоритма – такого объекта, который «умеет» выполнять эти действия.

Слово «алгоритм» происходит, как предполагают, от имени среднеазиатского (узбекского) математика XIII века Аль Хорезми (Абу Абдалла Мухаммед ибн Муса ал Хорезми ал Меджуси) – «Algorithmi» в латинской транскрипции, впервые сформулировавшего правила (процедуру) выполнения четырех арифметических действий в десятичной системе счисления.

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

Качество алгоритма определяется его свойствами (характеристиками). К основным свойствам алгоритма относятся [2]:

1. Массовость. Предполагается, что алгоритм может быть пригоден для решения всех задач данного типа. Например, алгоритм для решения системы линейных алгебраических уравнений должен быть применим к системе, состоящей из произвольного числа уравнений.

2. Результативность. Это свойство означает, что алгоритм должен приводить к получению результата за конечное число шагов.

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

4. Дискретность. Это свойство означает, что описываемый алгоритмом процесс и сам алгоритм могут быть разбиты на отдельные элементарные этапы, возможность выполнения которых на ЭВМ у пользователя не вызывает сомнений.

Сегодня на дворе «цифровое тысячелетие» и может создастся впечатление, что алгоритмам подвластны любые задачи. Оказывается, многие задачи не могут быть решены алгоритмически. Это так называемые алгоритмически неразрешимые задачи.

Для доказательства алгоритмической разрешимости или неразрешимости задач необходимы математически строгие и точные средства. В середине 30-х годов прошлого века были предприняты попытки формализовать понятие алгоритма и были предложены различные модели алгоритмов [19]: рекурсивные функции; «машины» – Тьюринга, Поста; нормальные алгорифмы Маркова.

Впоследствии было установлено, что эти и другие модели эквивалентны в том смысле, что классы решаемых ими задач совпадают [19]. Этот факт носит название тезиса Черча. Сейчас это общепризнанно. Формальное определение понятия алгоритма создало предпосылки для разработки теории алгоритма ещё до разработки первых ЭВМ. Прогресс вычислительной техники стимулировал дальнейшее развитие теории алгоритмов. Помимо установления алгоритмической разрешимости задач, теория алгоритмов занимается еще и оценкой сложности алгоритмов в смысле числа шагов (временная сложность) и требуемой памяти (пространственная сложность), а также занимается разработкой эффективных в этом смысле алгоритмов.

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

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

 

Схемы алгоритмов

 

Предписание о последовательности действий алгоритма может быть представлено так называемой схемой: логической схемой алгоритма, матричной схемой алгоритма, граф-схемой алгоритма.

Логическая схема алгоритма (ЛСА) впервые была предложена советским математиком Ляпуновым А.А. (1911-1973 гг.) в бытность его профессором кафедры математики военной артиллерийской (в те годы) академии им. Ф.Э. Дзержинского [36].

ЛСА – это выражение, состоящее из символов операторов, логических условий, следующих в определенном порядке, а также нумерованных стрелок, расставленных особым образом.

Матричная схема алгоритма (МСА) – это квадратная матрица, элементы которой указывают условия передачи управления от i-го оператора строки к j-ому оператору столбца. Строки матрицы нумеруются от первого оператора до предпоследнего, столбцы – от второго до последнего.

Граф-схема алгоритма (ГСА) – это ориентированный граф особого вида. Он содержит вершины четырех типов: 1) операторные, обозначаемые прямоугольниками; 2) условные, обозначаемые ромбами; 3) начальную и 4) конечную вершины, обозначаемые овалами. Вершины соединяются дугами.

Граф-схемы алгоритмов называют просто схемами и выполняют по ГОСТ 19.701-90 «Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения».

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

Таблица 68

Описание символов, используемых в схемах алгоритмов

 

Наименование	Обозначение	Функции
Данные		Символ отображает данные, носитель данных не определен. Используется для обозначения операций ввода и вывода данных.
Процесс		Символ отображает функцию обработки данных любого вида (выполнение определенной операции или группы операций, приводящее к изменению значения, формы или размещения информации). Используется для обозначения операций присваивания.
Предопределен-ный процесс		Символ отображает предопределенный процесс, состоящий из одной или нескольких операций или шагов, которые определены в другом месте (в подпрограмме, модуле). Используется для обозначения неэлементарных блоков.
Подготовка		Символ отображает модификацию команды или группы команд с целью воздействия на некоторую последующую функцию (установка переключателя, модификация индексного регистра или инициализация программы). Может быть использован для обозначения заголовка цикла.
Решение		Символ отображает решение или функцию переключательного типа, имеющую один вход и ряд альтернативных выходов, один и только один из которых может быть активизирован после вычисления условий, определенных внутри этого символа. Соответствующие результаты вычисления могут быть записаны по соседству с линиями, отображающими эти пути. Используется для обозначения оператора условного перехода или оператора варианта.
Граница цикла		Символ, состоящий из двух частей, отображает начало и конец цикла. Обе части символа имеют один и тот же идентификатор. Условия для инициализации, приращения, завершения и т.д. помещаются внутри символа в начале или в конце в зависимости от типа цикла.
Соединитель		Символ отображает выход в часть схемы и вход из другой части этой схемы и используется для обрыва линии и продолжения ее в другом месте. Соответствующие символы-соединители должны содержать одно и то же уникальное обозначение.
Терминатор		Символ отображает выход во внешнюю среду и вход из внешней среды. Используется для обозначения начала или окончания алгоритма.
Линия		Символ отображает поток данных или управления. Направления справа налево и снизу вверх обозначаются стрелками. Используется для соединения символов в алгоритме.
Параллельные действия		Символ отображает синхронизацию двух или более параллельных операций.
Пунктирная линия		Символ отображает альтернативную связь между двумя или более символами. Кроме того, символ используется для обведения аннотированного участка при записи комментариев.
Комментарий		Символ используется для добавления описательных комментариев или пояснительных записей с целью объяснений или примечаний. Пунктирные линии в символе комментария связаны с соответствующим символом или могут обводить группу символов. Текст комментариев или примечаний должен быть помещен около ограничивающей фигуры.

 

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

Алгоритм может быть реализован и схемой элементов (устройств), которые выполняются по ГОСТ 2.701-84 «Схемы. Виды и типы. Общие требования к выполнению».

Рекурсивные функции

Рекурсия – один из основных приемов программирования. Рекурсивные функции – функции, зависящие сами от себя. Когда мы рассматривали автоматы, то говорили о функциях переходов, которые в последующий момент автоматного времени зависят от своих значений в предыдущий момент времени. Так реализуется автоматная память. В теории рекурсивных функций, которая считается исторически первой формализацией понятия алгоритма, применяется нумерация слов в произвольном алфавите натуральными числами (N), и любой алгоритм сводится к вычислению некоторой функции при целочисленных значениях аргументов [22].

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

Функция полувычислима, если при задании входного набора, не принадлежащего области определения функции, алгоритм не заканчивает работу («зацикливается»). Теорию вычислимости разрабатывал А. Черч. Идея была похожа на изученную нами проблему функциональной полноты переключательных функций: выделить элементарные вычислимые функции (которые «интуитивно вычислимы») – то есть базис и предложить средства получения из этих элементарных вычислимых функций более сложных функций за конечное число шагов (как принцип суперпозиции в теории переключательных функций). Полученные таким образом функции тоже будут вычислимы.

Таковыми элементарными вычислимыми функциями являются:

1) S(x)=x+1, (N N), функция следования (указывает следующее натуральное число);

2) 0(х)=0, константа нуля;

3) I_m(x₁x₂…x_n)=x_m – проектирующая функция, результатом которой является выбор m-го из n аргументов.

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

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

Вторым оператором является оператор примитивной рекурсии.

Рассмотрим пример задания числового ряда Фибоначчи 1,1,2,3,5,8,13,21,… с использованием оператора примитивной рекурсии:

Здесь указываются два начальных значения функции f(0), f(1) и принцип формирования последующего значения. В отличие от функций переходов автомата, указывается не автоматное время, а шаг вычислений n, т.е. значение функции на некотором шаге, отличном от нулевого и первого, равно сумме значений функции на двух предыдущих шагах.

Тогда f(0)=1, f(1)=1, f(2)=f(0)+f(1)=1+1=2, f(3)=f(1)+f(2)=1+2=3, f(4)=f(2)+f(3)=2+3=5,…

Рассмотрим другой пример использования оператора примитивной рекурсии:

f(0)=1, f(1)=f(0)×1=1, f(2)=f(1)×2=2, f(3)=f(2)×3=6, …

Таким образом, мы задали функцию факториала: x!

Функции, получаемые из элементарных, путем конечного числа применений операторов суперпозиции и примитивной рекурсии, называются примитивно-рекурсивными. Рассматривается и более сложная рекурсия, например, кратная, по нескольким переменным одновременно [19].

Все ли функции являются примитивно – рекурсивными? Можно показать, что множество всех одноместных целочисленных функций типа N N, где N – множество натуральных чисел, несчётно, тем более это верно для функции типа Nⁿ N. Каждая примитивно-рекурсивная функция имеет конечное описание, т.е. задаётся конечным словом в некотором фиксированном для всех функций алфавите [19]. Множество всех конечных слов счётно, поэтому примитивно-рекурсивные функции образуют не более чем счётное подмножество несчётного множества функций типа Nⁿ N. Более того, оказывается, не все вычислимые функции можно описать как примитивно-рекурсивные.

Третьим оператором является оператор минимизации m, который позволяет вводить в вычисления перебор для определения нужного значения.

Например:

f(x₁x₂)=m(y–x₁=x₂);

Напомним, что x₁, x₂ являются натуральными числами. Такие функции называются частично рекурсивными, то есть они не полностью определенные, в отличие от полностью определенных примитивно-рекурсивных. В соответствие с тезисом Черча функция полувычислима, если и только если она частично рекурсивна.

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

Рекурсивные функции – основа функционального программирования. Примером языка функционального программирования является язык LISP, разработанный в 1960 г. Д Маккарти. Это один из первых языков обработки данных в символьной форме (LISP, от LISt Processing – обработка списков). Одним из наиболее существенных свойств языка LISP является то, что данные, программы и даже сам язык – представляют собой просто списки символов в скобках. Подобная структура позволяет писать программы или подпрограммы, способные обращаться сами к себе [37].

В LISP используется префиксная форма записи:

(+ху)=x+y;

(*х(+ху))=x*(x+y);

(+(*хх)(*уу))=x²+y².

Определение функций и их вычисление в языке основано на так называемом лямбда-исчислении, введенном в 1931 г. А Черчем:

λ(х₁,х₂,…,х_n)f_n или (lambda(xy)(+(*xx)(*yy))),

где λ – определение функции, х₁,…,х_n – формальные параметры (лямбда список), f_n – тело функции.

Рекурсии присутствуют и в языках структурного программирования.

Рассмотрим пример решения задачи на Паскале, использующий рекурсию [3].

З а д а ч а. Известно рекурсивное определение факториала:

Здесь n – неотрицательно. Записать эту функцию на языке Паскаль.

Решение. В первой строке определения явно указано, как вычислить факториал, если аргумент равен нулю или единице. В любом другом случае для вычисления n! необходимо вычислить предыдущее значение (n-1)! и умножить его на n. Уменьшающееся значение гарантирует, что в конце концов возникнет необходимость найти 1! или 0!, которые вычисляются непосредственно.

program task5;

var n:integer; {исходное значение}

function fact(i:integer):integer;

begin if (i=1) or (i=0)

then fact:=1

else fact:=fact(i-1)*i;

end;

begin write(’Введите нужное значение n ’);

readln(n);

writeln(’Факториал ’,n,’ равен ’,fact(n));

end.

Заметим, что на время выполнения вспомогательного алгоритма основной алгоритм приостанавливается. При вызове новой копии рекурсивного алгоритма вновь выделяется место для всех переменных, объявляемых в нем, причем переменные других копий будут недоступны. При удалении копии рекурсивного алгоритма из памяти удаляются и все его переменные. Активизируется предыдущая копия рекурсивного алгоритма, становятся доступными ее переменные. Пусть необходимо вычислить 4!. Основной алгоритм: вводится n=4, вызов fact(4). Основной алгоритм приостанавливается, вызывается и работает fact(4): 4<>1 и 4<>0, поэтому fact:=fact(3)*4. Работа функции приостанавливается, вызывается и работает fact(3): 3<>1 и 3<>0, поэтому fact:=fact(2)*3. В данный момент в памяти компьютера две копии функции fact. Вызывается и работает fact(2): 2<>1 и 2<>0, поэтому fact:=fact(1)*2. В памяти компьютера уже три копии функции fact и вызывается четвертая. Вызывается и работает fact(1): 1=1, поэтому fact(1)=1. Работа этой функции завершена, продолжает работу fact(2). fact(2):=fact(1)*2=1*2=2. Работа этой функции также завершена, и продолжает работу функция fact(3). fact(3):=fact(2)*3=2*3=6. Завершается работа и этой функции, и продолжает работу функция fact(4). fact(4):=fact(3)*4=6*4=24. После чего управление передается в основную программу и печатается ответ: «Факториал 4 равен 24».

 

Машина Тьюринга

 

Машина Тьюринга – одна из абстрактных моделей алгоритмов названа в честь английского математика Алана Тьюринга (1912-1954 гг.).

Машина Тьюринга включает [19]: 1) управляющее устройство, которое может находиться в одном из состояний, образующих конечное множество Y={y₁,y₂,...,y_k}; 2) ленту, разбитую на ячейки, в каждой из которых может быть записан один из символов конечного алфавита Х={х₁,х₂,...,х_p}; 3) устройство обращения к ленте – считывающую и записывающую головку, которая в каждый момент времени «обозревает» ячейку и, в зависимости от символа в ячейке и состояния управляющего устройства, записывает в эту ячейку новый символ (он может совпадать с прежним, считываемым) или пустой символ (прежний символ стирается и не его место записывается символ пробела). Далее устройство обращения сдвигается на ячейку влево или вправо или остается на месте. При этом управляющее устройство переходит в новое внутреннее состояние или остается в старом (текущем) состоянии. Среди состояний устройства управления выделяются начальное y₁ и заключительное y_k состояния (k – мнемонический знак окончания работы). В начальном состоянии машина Тьюринга находится перед началом работы, в конечном – после окончания работы.

Память машины Тьюринга – конечное множество состояний (внутренняя память) и лента (внешняя память). Лента бесконечна в обе стороны, однако в начальный момент времени только конечное число ячеек ленты заполнено символами, остальные пусты, т.е. содержат пустой символ – символ пробела l.

Данные машины Тьюринга – слова в алфавите ленты, на ленте записываются исходные данные и затем – результат.

Элементарные шаги – это считывание и запись символов, сдвиг головки, переход устройства управления из состояния в состояние.

На рис. 88 изображена структурная схема машины Тьюринга. Под воздействием входного символа х, например 1, считываемого головкой, устройство управления формирует выходной символ Z, управляет движением головки: влево (L), вправо (R), на месте (Е).

Рис. 88. Структурная схема машины Тьюринга

 

Полное состояние машины или конфигурация (или машинное слово), по которому однозначно определяется ее дальнейшее поведение, описывается внутренним состоянием y_i, символами слева и справа от головки, например:...x₁y_ix₂... Система команд машины содержит записи вида , где х₁ – читаемый символ в состоянии y₁; y₂ – новое внутреннее состояние; l – записываемый символ; R – признак продвижения головки, ® – символ перехода в новое состояние.

Совокупность всех команд называется программой. Каждая машина Тьюринга определяется своим алфавитом, состояниями внутренней памяти и программой.

Чтобы полностью определить работу машины, надо указать ее конфигурацию для начального момента времени. Будем считать, что в начальной конфигурации головка воспринимает самую левую непустую ячейку.

Машина Тьюринга задается тройкой – М=<X,Y,П>, где Х – алфавит символов ленты с выделенным пустым символом l (пробелом); Y – алфавит внутренних состояний с выделенными символами начального y₁ и конечного y_k состояний; П – программа, т.е. конечная последовательность упорядоченных пятерок символов – команд.

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

Пример 1. Рассмотрим машину Тьюринга, алфавит ленты которой содержит кроме символов пробела l символ 1. Будем представлять некоторое число «а» в виде а символов 1, например, l111l – число 3, l11111l – число 5. Машина, увеличивающая записанное число на единицу и возвращающаяся в исходное положение, реализуется следующей программой:

;

;

;

.

Работа машины может быть описана графом переходов (рис. 89), в котором дуги помечены условиями переходов (числитель), записываемыми символами и указанием направления движения головки (знаменатель).

 

Рис. 89. Граф переходов машины Тьюринга,

реализующий алгоритм увеличения числа на единицу

 

Последовательность работы машины, например, для слова l11l, описывается рис. 90. Вначале (исходное положение) головка находится у начала числа и по окончании работы должна установиться там же – у начала числа, увеличенного на 1.

Рис. 90. Последовательность работы машины Тьюринга,

реализующей алгоритм увеличения числа на единицу

 

Такая машина применима к любому слову в алфавите {l,1}.

Работа машины Тьюринга может быть описана таблицей (табл. 69).

 

Таблица 69

Работа машины Тьюринга

Внутреннее	Символ
состояние	l
y1
y2
yk

 

Строку с y_k можно опустить. В табл. 69 x_i – выходной символ, S_tÎ{L,R,E}.

Пример 2. [19]: Рассмотрим пример реализации алгоритма сложения чисел а и b, записанных на ленте в виде а и b единиц с разделителем *. Обозначим такую запись 1^а, 1^b. Следовательно, необходимо переработать слово 1^а*1^b в слово 1^а+b, т.е. удалить разделительный символ * и сдвинуть одно из слагаемых, скажем, первое ко второму (как на счетах).

Такой алгоритм осуществляет машина Тьюринга, граф переходов устройства управления которой изображен на рис. 91. Здесь в числителе – считываемый символ, в знаменателе – записываемый символ и знак управления движением головки.

Рис. 91. Граф переходов машины Тьюринга, реализующей алгоритм

сложения двух чисел, заданных единицами

 

Пусть, например, заданы числа 1² и 1¹. Тогда последовательность работы машины может быть описана рис. 92. В исходном положении головка установлена напротив начала первого числа (напротив первой его единицы). Головка на месте первой единицы записывает пробел l и движется до разделителя *, найдя который, записывает вместо него 1 и начинает движение влево, останавливается напротив первого пробела, а затем сдвигается вправо к первой единице.

На графе рис. 91 переход необходим для случая отсутствия первого числа, т.е. когда исходное слово имеет вид *1^b.

Рис. 92. Последовательность работы машины Тьюринга,

реализующей сложение чисел 1²(11) и 1¹(1)

 

Тогда система команд имеет вид:

Аналогично могут быть построены некоторые другие простые машины Тьюринга, в том числе машина для разветвления алгоритма, организации цикла и т.д. Из простых машин Тьюринга можно простроить более сложные путем композиции.

А. Тьюринг выдвинул следующую гипотезу.

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

Частичная числовая n-местная функция f(x₁,...,x_n) называется вычислимой по Тьюрингу, если существует машина, вычисляющая ее в следующем смысле:

1. Если набор значений аргументов принадлежит области определения функции f, то машина, начав работу в некоторой конфигурации, задающей значение аргументов, останавливается, заканчивая работу в конфигурации, соответствующей значению функции.

2. Если набор значений аргументов не принадлежит области определения функций f, то машина, начав работу в некоторой конфигурации, работает бесконечно, не приходя в заключительное состояние.

Машина Тьюринга – идеализированная модель ЭВМ. Она намного проще даже самых первых примитивных ЭВМ. Но для теоретических исследований она слишком громоздка. Поэтому получили распространение усовершенствования машины Тьюринга, одним из которых является многоленточная машина Тьюринга (рис. 93). Она имеет несколько входных лент и одну выходную, на которую записывается результат. Содержимое ячеек выходной ленты нельзя читать и корректировать. В такой машине полагается, что головки неподвижны, а ленты движутся, возможно в разных направлениях [36].

Такт работы это: одновременное считывание символов со всех лент, кроме выходной, смена состояния в зависимости от считанного набора символов, запись новых символов, сдвиг лент.

Рис. 93. Многоленточная машина Тьюринга

Машина Поста

Эмиль Пост – молодой американский математик – в 1936 г. предложил эту модель практически одновременно с А. Тьюрингом

В его машине тоже имеется бесконечная лента и головка. Лента разделена на ячейки. В каждой ячейке записан один символ из фиксированного алфавита. В любой момент времени машина обрабатывает ровно одну ячейку.

Машина Поста работает под управлением программы. Программа состоит из команд. Команды отличаются от команд машины Тьюринга. Если у Тьюринга все команды одного типа и похожи на функции переходов-выходов автомата, то у Поста команды больше напоминают машинные команды современных ЭВМ. Команды машины Поста состоят из трёх частей (полей) [7]:

1. Номер команды.

2. Операция.

3. Отсылка (номер следующей команды).

Команды нумеруются с 1. Первой выполняется команда 1.

Операции:

1. → – движение на одну клетку вправо (R).

2. ← – движение на одну клетке влево (L).

3. S – запись в обозреваемую ячейку, при этом предыдущее значение ячейки теряется (S – произвольный символ алфавита).

4. Ветвление

Si – символ в ячейке, М – номер следующей команды.

5. Стоп: HLT (ЕND).

При ветвлении символы Si должны быть различны, но не обязательно использовать весь алфавит. Если Si есть в ячейке, то выполняется команда Mi, при этом головка не перемещается и в клетку ничего не записывается. Если ни один символ не совпадает – происходит так называемая безрезультатная остановка.

Пример 1. Алфавит А: {1,λ}, где λ – пустой символ, как и в машинах Тьюринга.

1. R,2;

2. 1,1.

Это программа заполнения ленты символами 1, т.е. пустой ленты, в которой во всех ячейках – λ.

Пример 2. Прибавление символа 1 к числу 11...1, А={λ,1}.

1. R,2;

2.

3. 1,4;

4. HLT.

Это программа так называемого инкремента, то есть число, записанное «зарубками», «черточками», увеличивается на одну «черточку» при движении вправо.

Если же после прибавления двигаться влево к началу числа, как это обычно требуется, то:

4. L,5;

5.

6. λ,7;

7. R,8;

8. HLT.

Если работа алгоритма никогда не закончится над некоторыми исходными данными, то алгоритм неприменим к ним (хотя в примере 1 это и не так).

Алгоритм А над исходными данными X обозначим А(Х) – это результат работы алгоритма. Результат не определен, если А неприменим к Х.

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

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