ЕГЭ-12. Выполнение алгоритмов для исполнителя (МТ)

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

Программа работы исполнителя задаётся таблицей. В первой строке таблицы перечислены все возможные символы, которые могут находиться в текущей ячейке ленты, в первом столбце — все возможные состояния головки. На пересечении i-й строки и j-го столбца таблицы находится команда, которую должна выполнить машина Тьюринга, если головка находится в состоянии, соответствующем i-й строке, и обозревает символ, соответствующий j-му столбцу. Если для некоторой пары «символ — состояние» команда в таблице отсутствует, это означает, что такая пара при работе исполнителя не встречается.

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

Например, команда 0, L, q3 означает следующее: в текущую ячейку записывается символ «0», затем головка сдвигается на одну ячейку влево и переходит в состояние q3.

Выполните задание. На ленте записана последовательность из нулей и единиц; её длина равна {1}. Ячейки вне последовательности заполнены символом «λ». В начальном состоянии q0 головка обозревает ближайшую пустую ячейку справа от последовательности.

Программа работы исполнителя:

Известно, что после выполнения программы количество нулей на ленте оказалось равно {3}. Определите {4} в исходной последовательности. Ответ запишите целым числом.

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

Программа работы исполнителя задаётся таблицей. В первой строке таблицы перечислены все возможные символы, которые могут находиться в текущей ячейке ленты, в первом столбце — все возможные состояния головки. На пересечении i-й строки и j-го столбца таблицы находится команда, которую должна выполнить машина Тьюринга, если головка находится в состоянии, соответствующем i-й строке, и обозревает символ, соответствующий j-му столбцу. Если для некоторой пары «символ — состояние» команда в таблице отсутствует, это означает, что такая пара при работе исполнителя не встречается.

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

Например, команда 0, L, q3 означает следующее: в текущую ячейку записывается символ «0», затем головка сдвигается на одну ячейку влево и переходит в состояние q3.

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

Программа работы исполнителя:

После выполнения программы на ленте оказалась двоичная запись числа {3}. Определите десятичное значение наибольшего числа, меньшего, чем {1}, которое могло быть записано на ленте до начала работы программы. Ответ запишите в десятичной системе счисления.

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

Программа работы исполнителя задаётся таблицей. В первой строке таблицы перечислены все возможные символы, которые могут находиться в текущей ячейке ленты, в первом столбце — все возможные состояния головки. На пересечении i-й строки и j-го столбца таблицы находится команда, которую должна выполнить машина Тьюринга, если головка находится в состоянии, соответствующем i-й строке, и обозревает символ, соответствующий j-му столбцу. Если для некоторой пары «символ — состояние» команда в таблице отсутствует, это означает, что такая пара при работе исполнителя не встречается.

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

Например, команда 0, L, q3 означает следующее: в текущую ячейку записывается символ «0», затем головка сдвигается на одну ячейку влево и переходит в состояние q3.

Выполните задание. На ленте записана двоичная запись натурального числа {1} без ведущих нулей. В начальном состоянии q0 головка обозревает ближайшую пустую ячейку «λ»: слева от записи, если первая команда сдвигает головку вправо (R), и справа от записи, если влево (L). Ячейки вне записи заполнены символом «λ».

Программа работы исполнителя:

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

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

Программа работы исполнителя задаётся таблицей. В первой строке таблицы перечислены все возможные символы, которые могут находиться в текущей ячейке ленты, в первом столбце — все возможные состояния головки. На пересечении i-й строки и j-го столбца таблицы находится команда, которую должна выполнить машина Тьюринга, если головка находится в состоянии, соответствующем i-й строке, и обозревает символ, соответствующий j-му столбцу. Если для некоторой пары «символ — состояние» команда в таблице отсутствует, это означает, что такая пара при работе исполнителя не встречается.

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

Например, команда 0, L, q3 означает следующее: в текущую ячейку записывается символ «0», затем головка сдвигается на одну ячейку влево и переходит в состояние q3.

Выполните задание. На ленте записана двоичная запись натурального числа {1} без ведущих нулей. В начальном состоянии q0 головка обозревает ближайшую пустую ячейку «λ»: слева от записи, если первая команда сдвигает головку вправо (R), и справа от записи, если влево (L). Ячейки вне записи заполнены символом «λ».

Программа работы исполнителя:

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

(И. Карпачёв) На ленте исполнителя МТ в соседних ячейках записана последовательность из 1000 символов, состоящей из 764 двоек, 122 троек и 114 символов Х, расположенных в указанном порядке. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности. Программа для исполнителя:

Команды движения каретки: L – влево, R – вправо, S – стоп. Какую десятичную цифру необходимо указать вместо символа Х, чтобы сумма цифр последовательности после выполнения программы равнялась 3496?

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

Команды движения каретки: L – влево, R – вправо, S – стоп. После выполнения программы на ленте осталось 200 нулей. Определите максимально возможное количество единиц, которое могло быть в исходной последовательности.