Лекция № 2. Машина Поста и нормальные алгорифмы Маркова
1. Машина Поста.
2. Нормальные алгорифмы Маркова.
Абстрактную математическую модель, получившую название «машина Поста», разработал американский математик Эмиль Пост (1987 – 1954).
Неформальное описание этой модели выглядит следующим образом.
Эмиль Пост
Имеется воображаемый Исполнитель – каретка, передвигающаяся вдоль бесконечной ленты разбитой на секции. Секция может быть пустой, или же в ней может находиться метка (рис. 3).
V
V
Ý – каретка метка метка
Рис. 3. Машина Поста
По командам каретка может передвигаться на одну секцию влево или вправо, ставить или стирать метку в секции, напротив которой она находится. Работает машина Поста по программе, представляющей собой последовательность пронумерованных команд. Их всего 6. Записываются эти команды так.
Система команд машины Поста
Формат
Пример
Описание примера
ξ <№>
1. ξ 2
При исполнении команды ξ 2, записанной под номером 1, стирается метка в секции, напротив которой расположена каретка, затем осуществляется переход к выполнению команды под номером 2.
→ <№>
2. → 3
При исполнении команды → 3,записанной под номером 2, каретка сдвигается на одну секцию вправо, затем осуществляется переход к выполнению команды под номером 3.
← <№>
10. ← 11
При исполнении команды ← 11,записанной под номером 10, каретка сдвигается на одну секцию влево, затем осуществляется переход к выполнению команды под номером 11.
V <№>
4. V 5
При исполнении команды V 5,записанной под номером 4,ставитсяметка в секции, напротив которой расположена каретка, затем осуществляется переход к выполнению команды под номером 5.
? <№1>,<№2>
3. ? 4, 2
При исполнении команды ? 4, 2,записаннойпод номером 3, если в секция, напротив которой располагается каретка, оказывается пустой, то осуществляется переход к выполнению команды под номером 4, в противном случае осуществляется переход к команде под номером 2.
Стоп
12. стоп
При исполнении команды стоп записаннойпод номером 12, выполнение программы останавливается
Для выполнения любой программы необходимо задать так называемое начальное состояние ленты, обязательно указав положение каретки.
Пример 2.1.1. Пусть начальное состояние имеет вид:
V
V
V
V
V
V
V
Ý
Пусть также дана программа машины Поста:
1.
ξ 2
4.
V 5
7.
ξ 8
10.
← 11
2.
→ 3
5.
→ 6
8.
→ 9
11.
? 10 , 2
3.
? 4, 2
6.
? 5, 7
9.
? 12, 10
12.
стоп
В результате выполнения этой программы при заданном начальном состоянии лента примет вид:
V
V
V
V
V
V
V
Заметим, что начальное состояние можно рассматривать как запись на ленте двух чисел 4 и 3 в унарной системе счисления. Соответственно, результат программы представляет собой запись в унарной системе счисления числа 7. В этом контексте правомерной выглядит гипотеза о том, что приведенная программа – программа сложения натуральных чисел, записанных в унарной системе счисления. Как и всякая гипотеза, она требует проверки.
Относительно любых программ машины Поста полагается, что:
1) команды в программе нумеруются с 1 и записываются по порядку;
2) для каждой ссылки, имеющейся в командах программы, в программе найдется номер команды равный указанной ссылке.
Если в ходе выполнения программы машина доходит до выполнения невыполнимой команды (печати метки в непустой секции, стирания метки в пустой секции), то считается, что работа программы приводит к безрезультатной остановке. Результативной остановкой принято считать остановку работы программы по команде стоп.
В том случае, когда работа машины не приводит к безрезультатной или результативной остановке, говорят, что процесс работы машины Поста происходит бесконечно. При этом различные программы при одном и том же начальном состоянии могут приводить к результативной остановке, безрезультатной остановке, безостановочной работе машины. Точно также, при различных исходных состояниях результат одной и той же программы может быть различным.
Пример 2.1.2.
Начальное состояние
Программа
Результат
а)
1.
? 3, 1
а) результативная остановка
2.
ξ 4
б)
3.
→ 2
б) безостановочная работа
4.
Стоп
в)
в) безрезультатная остановка(при исполнении команды 2)
Определение 2.1.1.Функция f: Nk→ N (k=1, 2,..¥) называется вычислимой на машине Поста, если существует программа p машины Поста, вычисляющая функцию f(x1, x2, … xk), то есть обладающая следующими свойствами:
а) если f(x1, x2, … xk)=y, то результатом работы программы p при заданном наборе данных <x1, x2, … xk>, будетзаписанное на ленте число y;
б) если значение f(x1, x2, … xk) не определено, то применение программы p не приводит к результативной остановке.
Простейшими вычислимыми по Посту функциями являются f(x)=0, f(x)=1. В то же время справедлива следующая теорема.
Теорема 2.1.1. Существует числовая всюду определенная функция, которая не вычислима на машине Поста.
Доказательство. Количество программ машины Поста, длина которых фиксирована, конечно. Выписывая подряд (в любом порядке) все программы дины 1, затем длины 2 и т.д. можно получить последовательность p0, p1, p2, … pn, … всех программ машины Поста. Иными словами, множество программ машины Поста не более чем счетно.
Определим функцию f(n): N→ Nследующим образом:
f(n)=0, если применение программы pnк числу nне приводит к результативной остановке или результат не есть запись натурального числа;
f(n)=k+1, если применение программы pnк числу nдает результат, являющийся записью числа k.
Докажем, что так всюду определенная функция f(n) не вычислима на машине Поста. Доказательство проведем от противного.
Пусть существует программа машины Поста ps, вычисляющая функцию f(n). Тогда возможно два случая.
1. Применение программы psк числу s приводит к результативной остановке и в результате на ленте оказывается запись натурального числа k. В этом случае по определению функции f(n) f(s)=k+1 и, так как k+1¹k, то psне вычисляет f(n) и налицо противоречие с нашим предположением.
2. Применение программы psк числу s приводит к безрезультатной остановке или результат не является записью натурального числа. В этом случае противоречие с нашим предположением очевидно, поскольку функция определена f(n) всюду.
Эмиль Пост
а)
б)
в)