1. Введение
В задании нужно проследить работу исполнителя МТ: определить символ под головкой, найти подходящую команду в таблице и выполнить её. Главная сложность здесь не в вычислениях, а во внимательном переходе от одного шага к следующему.
Для решения не требуется писать программу. Достаточно понимать устройство ленты, обозначения в таблице и порядок выполнения команды.
Главная мысль. Большой текст в начале задачи — это справка о правилах работы МТ. Обычно он не меняется. В конкретной задаче нужно внимательно читать часть после слов «Выполните задание» и таблицу программы.
2. Теория
2.1. Что представляет собой исполнитель МТ
Исполнитель МТ работает с бесконечной лентой, разделённой на одинаковые ячейки. В каждой ячейке находится один символ. Пустая ячейка обозначается символом λ.
Над одной из ячеек расположена головка. Она видит только текущую ячейку и за один такт может записать в неё символ, сдвинуться на одну ячейку влево или вправо либо остаться на месте.
Кроме положения на ленте, у головки есть состояние: q₀, q₁, q₂ и так далее. Начальное состояние всегда указано в условии; в стандартной формулировке это q₀.
2.2. Как устроена команда
Каждая команда состоит из трёх элементов. Например, команда 0, L, q₃ означает: записать 0 в текущую ячейку, сдвинуть головку на одну ячейку влево и перейти в состояние q₃.
L — сдвиг влево; R — сдвиг вправо; N — головка остаётся в текущей ячейке; S — выполнить запись и завершить работу.
Важно: сначала изменяется текущая ячейка, только после этого головка двигается. Записываемый символ относится не к соседней, а именно к той ячейке, которую головка обозревает сейчас.
2.3. Как выполняется один шаг
Чтобы выбрать команду, нужно совместить текущее состояние и символ под головкой. Состояние задаёт строку таблицы, символ — столбец. На их пересечении находится команда.
Если нужная клетка таблицы пуста, команда для такой пары «состояние + символ» не определена, поэтому исполнитель останавливается. Если в самой команде стоит S, работа завершается сразу после выполнения этой команды.
2.4. Небольшие примеры команд
1, R, q₂. В текущую ячейку записывается 1, головка переходит вправо, новым состоянием становится q₂.
λ, N, q₁. Текущая ячейка очищается, головка остаётся на месте, состояние меняется на q₁.
0, S, q₃. В текущую ячейку записывается 0, после чего программа завершается. Дальнейший поиск команды не выполняется.
2.5. Разбор условия задачи
В задаче на ленте записано двоичное представление числа 2028 без ведущих нулей. Справа и слева находятся пустые ячейки λ. В начале головка стоит в первой пустой ячейке справа от числа и находится в состоянии q₀.
Переведём число в двоичную систему: 2028₁₀ = 11111101100₂. Значит, начальная запись имеет вид λ 11111101100 λ, причём головка находится над правым λ.
Программа работы исполнителя
| Состояние | λ | 0 | 1 |
|---|---|---|---|
| q₀ | λ, L, q₁ | ||
| q₁ | λ, L, q₂ | 0, L, q₁ | 1, L, q₁ |
| q₂ | 1, R, q₃ | ||
| q₃ | 0, S, q₃ |
Пустая клетка означает, что команда для этой пары не задана.
Пошаговое выполнение
Шаг 1 — вход в число. Головка находится в состоянии q₀ и видит λ. Используем команду λ, L, q₁: пустой символ не меняется, головка сдвигается на последний разряд числа и переходит в q₁.
Шаг 2 — проход влево. В состоянии q₁ для символов 0 и 1 команды устроены одинаково: символ сохраняется, головка движется влево и остаётся в q₁. Поэтому не нужно отдельно расписывать все 11 тактов — головка просто проходит через всю двоичную запись, не меняя её.
Шаг 3 — выход за левую границу. Когда головка доходит до λ слева от числа, выполняется λ, L, q₂. Она сдвигается ещё на одну пустую ячейку влево и переходит в q₂.
Шаг 4 — добавление единицы. В состоянии q₂ над λ выполняется 1, R, q₃: в ячейку записывается 1, затем головка возвращается вправо.
Шаг 5 — добавление нуля и остановка. В состоянии q₃ головка снова видит λ. Команда 0, S, q₃ записывает 0 и завершает программу.
3. Что может попасться
В задании могут попросить не только определить итоговую запись, но и восстановить свойства исходной последовательности. Ниже разобраны три основных варианта: задача на максимум, дописывание битов и поразрядное преобразование числа.
3.1. Максимально возможное число нулей
Условие
На ленте в соседних ячейках записана последовательность из 400 символов, среди которых могут быть только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами λ. В начальный момент головка расположена в ближайшей ячейке справа от последовательности.
После выполнения программы на ленте осталось ровно 100 нулей. Определите максимально возможное число нулей в исходной последовательности.
Программа работы исполнителя
| Состояние | λ | 1 | 0 |
|---|---|---|---|
| q₀ | λ, L, q₁ | ||
| q₁ | λ, R, q₂ | 0, R, q₂ | 1, L, q₁ |
| q₂ | λ, S, q₂ | 1, R, q₂ | 1, R, q₂ |
Пустая клетка означает, что команда для этой пары не задана.
Нюанс задачи. Здесь не нужно моделировать все 400 ячеек. Достаточно понять, какие символы изменяются слева и справа от первой единицы, найденной при движении справа налево.
Решение
Шаг 1 — вход в последовательность. В состоянии q₀ головка стоит над правым λ. Команда λ, L, q₁ перемещает её на последний символ и переводит в q₁.
Шаг 2 — обработка нулей справа. Если q₁ видит 0, выполняется 1, L, q₁. Ноль заменяется единицей, а головка продолжает движение влево. Поэтому все нули в конце исходной последовательности превращаются в единицы.
Шаг 3 — встреча с единицей. Когда q₁ впервые встречает 1, используется команда 0, R, q₂. Эта единица превращается в ноль, после чего головка разворачивается и начинает движение вправо.
Шаг 4 — проход вправо. В состоянии q₂ и 0, и 1 заменяются на 1. Значит, справа от найденной единицы после завершения программы нулей не останется.
Шаг 5 — считаем нули после работы. В результате сохраняются только нули, которые находились левее найденной единицы, и добавляется ещё один ноль — та самая единица, которую q₁ заменила на 0.
По условию в результате получилось 100 нулей. Один из них появился вместо единицы, поэтому слева от неё должно быть ровно 99 исходных нулей.
Шаг 6 — получаем максимум. Чтобы нулей в исходной строке было как можно больше, оставляем только одну обязательную единицу. Перед ней ставим 99 нулей, а оставшиеся 300 позиций после неё также заполняем нулями. Всего получается 99 + 300 = 399 нулей.
Ответ: 399
3.2. Дописывание битов к числу
Условие
На ленте в соседних ячейках записано двоичное представление числа 2027 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами λ. В начальный момент головка расположена в ближайшей слева от последовательности ячейке.
Определите результат работы программы. В ответе запишите получившееся на ленте число в десятичной системе счисления.
Программа работы исполнителя
| Состояние | λ | 0 | 1 |
|---|---|---|---|
| q₀ | λ, R, q₁ | ||
| q₁ | 1, R, q₂ | 0, R, q₁ | 1, R, q₁ |
| q₂ | 1, R, q₃ | ||
| q₃ | λ, S, q₃ |
Пустая клетка означает, что команда для этой пары не задана.
Нюанс задачи. Команды для 0 и 1 в состоянии q₁ сохраняют цифры. Поэтому важнее проследить не каждый разряд, а действия головки после выхода за правую границу числа.
Решение
Шаг 1 — переводим число в двоичную систему. 2027₁₀ = 11111101011₂.
Шаг 2 — входим в число слева. В состоянии q₀ головка видит λ и выполняет λ, R, q₁. Она переходит на первый разряд числа.
Шаг 3 — проходим исходную запись. В состоянии q₁ команда для 0 имеет вид 0, R, q₁, а для 1 — 1, R, q₁. Каждый разряд сохраняется, головка только двигается вправо.
Шаг 4 — записываем первую единицу. После последнего разряда головка оказывается над λ. Команда 1, R, q₂ заменяет этот λ на 1 и сдвигает головку ещё правее.
Шаг 5 — записываем вторую единицу. В состоянии q₂ головка снова видит λ и выполняет 1, R, q₃. Справа появляется ещё одна единица.
Шаг 6 — останавливаемся. В q₃ над следующим λ выполняется λ, S, q₃. Исходная двоичная запись не изменилась, к ней справа добавилось 11: 1111110101111₂.
Приписать справа два бита 11 — это умножить исходное число на 4 и прибавить 3. Поэтому 2027 · 4 + 3 = 8111.
Ответ: 8111
3.3. Поразрядное преобразование
Условие
На ленте в соседних ячейках записано двоичное представление числа 1022 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами λ. В начальный момент головка расположена в ближайшей справа от последовательности ячейке.
Определите десятичное значение числа на ленте после выполнения программы.
Программа работы исполнителя
| Состояние | λ | 1 | 0 |
|---|---|---|---|
| q₀ | λ, L, q₁ | ||
| q₁ | 1, L, q₂ | 0, L, q₃ | |
| q₂ | λ, S, q₂ | 0, L, q₃ | 1, L, q₂ |
| q₃ | λ, S, q₃ | 1, L, q₂ | 0, L, q₃ |
Пустая клетка означает, что команда для этой пары не задана.
Нюанс задачи. Здесь состояния q₂ и q₃ чередуются при обработке единиц. Удобнее выписать их закономерность, чем каждый раз заново искать команду в таблице.
Решение
Шаг 1 — переводим число в двоичную систему. 1022 = 2¹⁰ − 2, поэтому 1022₁₀ = 1111111110₂.
Шаг 2 — переходим на последний разряд. В q₀ над правым λ выполняется λ, L, q₁. Головка оказывается над последним символом 0.
Шаг 3 — обрабатываем последний ноль. Для пары q₁ и 0 используется команда 0, L, q₃. Последний разряд остаётся нулём, а головка сдвигается влево и переходит в q₃.
Шаг 4 — находим закономерность для единиц. В q₃ единица сохраняется и состояние меняется на q₂. В q₂ следующая единица заменяется на 0, после чего состояние снова становится q₃. Значит, при движении справа налево единицы по очереди превращаются в 1, 0, 1, 0 и так далее.
Шаг 5 — записываем результат. Перед последним нулём находятся девять единиц. После чередования они дают 101010101, а последний ноль не меняется. На ленте получается 1010101010₂.
Шаг 6 — переводим ответ в десятичную систему. 1010101010₂ = 2⁹ + 2⁷ + 2⁵ + 2³ + 2¹ = 512 + 128 + 32 + 8 + 2 = 682.
Ответ: 682
Видео разбор
Так-же все основные прототипы разбираются в формате видео разбора