Олимпиадный тренинг

Задача . ТР03. Задание 12. Машина Тьюринга: копирование последовательности


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

Время работы исполнителя делится на дискретные такты — шаги. На каждом такте головка находится в одном из допустимых состояний q0, q1, … . В начальный момент головка находится в состоянии q0.

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

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

Каждая команда состоит из трёх элементов, разделённых запятыми:

  1. символ, записываемый в текущую ячейку;
  2. направление: L — сдвиг на одну ячейку влево, R — сдвиг на одну ячейку вправо, S — завершение работы после записи символа без сдвига;
  3. состояние, в которое переходит головка.

Например, команда X, L, q2 означает: записать X в текущую ячейку, сдвинуться в соседнюю слева ячейку и перейти в состояние q2. Запись символа производится до сдвига.

Пример выполнения программы

Пусть на ленте подряд записаны три символа Z, остальные ячейки пусты, головка находится на первой пустой ячейке справа от слова ZZZ в состоянии q0. Для этой иллюстрации используется следующая программа:

СостояниеλZX
q0λ, L, q0X, L, q1
q1λ, S, q1X, L, q1

Начальное расположение ленты и головки:

…λλZZZλλ…
▲ q0

Лента и головка после остановки:

…λλXXXλλ…
▲ q1

Головка перемещается влево, заменяет все Z на X и останавливается на первой пустой ячейке слева от слова XXX. Пример поясняет правила чтения таблицы и не является программой основного задания.

Выполните задание

Алфавит исполнителя: {λ, 1, X, Z}. На ленте в соседних ячейках записано неизвестное ненулевое количество символов 1. Сразу справа от них записан один символ Z. Все остальные ячейки ленты заполнены символом λ.

В начальный момент головка расположена над самым левым символом 1 в состоянии q0. Программа работы исполнителя:

Состояниеλ1XZ
q0X, R, q1X, R, q0Z, L, q4
q11, R, q1X, R, q1Z, R, q2
q21, L, q31, R, q2
q3λ, R, q01, L, q3X, L, q3Z, L, q3
q4λ, S, q41, L, q4

После завершения программы на ленте находится 4054 символа 1. Определите количество символов 1, находившихся на ленте до начала работы программы. В ответе запишите целое число.