Программа машины Поста

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

Каждая программа машины Поста состоит из команд. Командой машины Поста будем называть выражение, имеющее один из следующих шести видов (буквы i, j, j₁, j₂ означают всюду натуральные числа 1,2,3,4,5,...):

Первый вид. Команды движения вправо

Второй вид. Команды движения влево

Третий вид. Команды печатания метки

Четвертый вид. Команды стирания метки

Пятый вид. Команды передачи управления

.

Шестой вид. Команды остановки

Например,

является командой движения вправо,

— командой передачи управления, а

6386. стоп

— командой остановки.

Число 1, стоящее в начале команды, называется номером команды. Так, у приведенных только что команд номера суть соответственно 137, 25 и 6386. Число j, стоящее в конце команды (а у команд передачи управления — каждое из чисел j₁ и j₂), будем называть отсылкой (при этом в команде передачи управления j₁ — верхней, а j₂— нижней отсылкой). У команд остановки нет отсылки. Так, у приведенных только что команд отсылками служат числа 1, 32, 25, причем 32 — верхняя отсылка, а 25 — нижняя отсылка.

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

1) На первом место в этом списке стоит команда с номером 1, на втором месте (если оно есть) — команда с номером 2 и т. д.; вообще на А-м месте стоит команда с номером Н.

2) Отсылка любой из команд списка совпадает с номером некоторой (другой или той же самой) команды списка (более точно: для каждой отсылки каждой команды списка найдется в списке такал команда, номер которой равен рассматриваемой отсылке).

Например, следующий список будет программой машины Поста:

А эти два списка не будут программами машины Поста, хотя и составлены из команд машины Поста:

(не выполнено первое условие);

(не выполнено второе условие).

Для наглядности программы машины Поста мы будем записывать столбиком. Число команд программы называется длиной программы.

Упражнение. Выпишите все программы машины Поста длины l. Сколько существует программ. длины 2, длины 3, длины n?