1. Как на ЕГЭ (1). Машина Тьюрига

 

Исполнитель МТ представляет собой читающую и записывающую головку, которая  может  передвигаться  вдоль  бесконечной  горизонтальной  ленты, разделённой  на  равные  ячейки.  В каждой  ячейке  находится  ровно  один символ из алфавита исполнителя (множество символов \(A = {a0, a1, ..., a(n–1)})\), включая специальный пустой символ \(a0\).  Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний \(Q =  {q0, q1,  ..., q(n–1)}\).  В  начальный  момент  времени  головка  находится в начальном состоянии \(q0\).  На  каждом  такте  головка  обозревает  одну  ячейку  ленты,  называемую текущей ячейкой.  За один такт головка исполнителя может переместиться в ячейку справа или слева от текущей, не меняя находящийся в ней символ, или заменить символ в текущей ячейке без сдвига в соседнюю ячейку. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии. Программа работы исполнителя МТ задаётся в табличном виде.

 

	\(a0\)	\(a1\)	...	\(a(n-1)\)
\(q0\)	команда	команда	...	команда
\(q1\)	команда	команда	...	команда
...	...	...	...	...
\(q(n-1)\)	команда	команда	...	команда

В  первой  строке  перечислены  все  возможные  символы  в  текущей  ячейке ленты, в первом столбце — возможные состояния головки. На пересечении  \(i\)-й строки и \(j\)-го столбца находится команда, которую выполняет МТ, когда головка  обозревает \(j\)-й символ, находясь в \(i\)-м  состоянии. Если  пара «символ — состояние» невозможна, то клетка для команды остаётся пустой. Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент  —  записываемый  в  текущую  ячейку  символ  алфавита  (может совпадать  с  тем,  который  там  уже  записан).  Второй  элемент — один  из четырёх символов «L», «R», «N», «S». Символы «L» и «R» означают сдвиг в левую или правую ячейки соответственно, «N» — отсутствие сдвига, «S» — завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг  происходит  после  записи  символа  в  текущую  ячейку.  Третий элемент — новое состояние головки после выполнения команды.  Например, команда \(0\), L, \(q3\)  выполняется  следующим  образом:  в текущую ячейку  записывается  символ  «\(0\)»,  затем  головка  сдвигается  в  соседнюю слева ячейку и переходит в состояние \(q3\).

 

Приведём пример выполнения программы, заданной таблично.
На  ленте  записано  неизвестное  ненулевое  количество  расположенных подряд в соседних ячейках символов «Z», все остальные ячейки ленты заполнены  пустым  символом  «λ».  В  начальный  момент  времени  головка находится на неизвестном ненулевом расстоянии справа от самого правого символа «Z».

 

Программа

 

 

заменяет  на  ленте  все  символы  «Z»  на  «X»  и  останавливает  исполнителя  в первой ячейке слева от последовательности символов «X». 

Возможное начальное состояние исполнителя:

 

 

 

Конечное состояние исполнителя после завершения выполнения программы:

 

 

 

На ленте в соседних ячейках записана последовательность из \(1000\) символов, включающая   только   нули   и   единицы.   Ячейки   справа   и   слева  от  последовательности  заполнены пустыми  символами  «λ».  В  начальный момент  времени  головка  расположена  в  ближайшей  ячейке  справа  от последовательности. Программа работы исполнителя:  

 

	λ	\(1\)	\(0\)
\(q0\)	λ, L, \(q1\)
\(q1\)	λ, S, \(q1\)	\(0\), S, \(q1\)	\(1\), L, \(q1\)

 

После  выполнения  программы на ленте осталось ровно 346 нулей. Определи максимально возможное число нулей в исходной последовательности.