Машина Поста

Лекция № 2. Машина Поста и нормальные алгорифмы Маркова

1. Машина Поста.

2. Нормальные алгорифмы Маркова.

Абстрактную математическую модель, получившую название «машина Поста», разработал американский математик Эмиль Пост (1987 – 1954). Неформальное описание этой модели выглядит следующим образом.

Эмиль Пост

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

Ý – каретка метка метка

Рис. 3. Машина Поста

По командам каретка может передвигаться на одну секцию влево или вправо, ставить или стирать метку в секции, напротив которой она находится. Работает машина Поста по программе, представляющей собой последовательность пронумерованных команд. Их всего 6. Записываются эти команды так.

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

Пример 2.1.1. Пусть начальное состояние имеет вид:

Пусть также дана программа машины Поста:

В результате выполнения этой программы при заданном начальном состоянии лента примет вид:

Заметим, что начальное состояние можно рассматривать как запись на ленте двух чисел 4 и 3 в унарной системе счисления. Соответственно, результат программы представляет собой запись в унарной системе счисления числа 7. В этом контексте правомерной выглядит гипотеза о том, что приведенная программа – программа сложения натуральных чисел, записанных в унарной системе счисления. Как и всякая гипотеза, она требует проверки.

Относительно любых программ машины Поста полагается, что:

1) команды в программе нумеруются с 1 и записываются по порядку;

2) для каждой ссылки, имеющейся в командах программы, в программе найдется номер команды равный указанной ссылке.

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

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

Пример 2.1.2.

Начальное состояние	Программа	Результат
а)	1.	? 3, 1	а) результативная остановка
2.	ξ 4
б)	3.	→ 2	б) безостановочная работа
4.	Стоп
в)			в) безрезультатная остановка (при исполнении команды 2)

Определение 2.1.1.Функция f: N^k→ N (k=1, 2,..¥) называется вычислимой на машине Поста, если существует программа p машины Поста, вычисляющая функцию f(x₁, x₂, … x_k), то есть обладающая следующими свойствами:

а) если f(x₁, x₂, … x_k)=y, то результатом работы программы p при заданном наборе данных <x₁, x₂, … x_k>, будет записанное на ленте число y;

б) если значение f(x₁, x₂, … x_k) не определено, то применение программы p не приводит к результативной остановке.

Простейшими вычислимыми по Посту функциями являются f(x)=0, f(x)=1. В то же время справедлива следующая теорема.

Теорема 2.1.1. Существует числовая всюду определенная функция, которая не вычислима на машине Поста.

Доказательство. Количество программ машины Поста, длина которых фиксирована, конечно. Выписывая подряд (в любом порядке) все программы дины 1, затем длины 2 и т.д. можно получить последовательность p₀, p₁, p₂, … p_n, … всех программ машины Поста. Иными словами, множество программ машины Поста не более чем счетно.

Определим функцию f(n): N→ N следующим образом:

f(n)=0, если применение программы p_n к числу n не приводит к результативной остановке или результат не есть запись натурального числа;

f(n)=k+1, если применение программы p_n к числу n дает результат, являющийся записью числа k.

Докажем, что так всюду определенная функция f(n) не вычислима на машине Поста. Доказательство проведем от противного.

Пусть существует программа машины Поста p_s, вычисляющая функцию f(n). Тогда возможно два случая.

1. Применение программы p_s к числу s приводит к результативной остановке и в результате на ленте оказывается запись натурального числа k. В этом случае по определению функции f(n) f(s)=k+1 и, так как k+1¹k, то p_s не вычисляет f(n) и налицо противоречие с нашим предположением.

2. Применение программы p_s к числу s приводит к безрезультатной остановке или результат не является записью натурального числа. В этом случае противоречие с нашим предположением очевидно, поскольку функция определена f(n) всюду.

¨Теорема доказана.