Исполнитель МТ (машина Тьюринга): как читать программу
Коротко
Исполнитель МТ — головка, которая движется по бесконечной ленте из ячеек. В каждой ячейке один символ алфавита, включая пустой символ. На каждом такте головка в некотором состоянии q обозревает текущую ячейку и выполняет команду из таблицы: записывает символ, сдвигается влево (L) или вправо (R) либо останавливается (S) и переходит в новое состояние. В демоверсии ЕГЭ 2027 это задание 12. Надёжный способ решения — пошагово смоделировать работу программы, в том числе на Python.
Устройство (по демоверсии 2027)
- Лента бесконечна, в каждой ячейке ровно один символ алфавита A = {a0, …, an–1}; a0 — пустой символ (часто λ).
- Состояния Q = {q0, …, qn–1}, начальное — q0.
- Программа — таблица: строки — состояния, столбцы — символы.
- Команда «символ, сдвиг, состояние»: например, 0, L, q3 — записать 0, сдвинуться влево, перейти в q3.
- Сдвиг выполняется после записи; S — остановка после текущей команды.
Пример
Программа: в q0 на «1» — 1, R, q0; на «λ» — 1, S, q0. Лента: 111, головка на левой единице. Головка идёт вправо по единицам и на первой пустой ячейке пишет 1 и останавливается: 1111, тактов — 4.
Моделирование на Python
tape = {0: '1', 1: '1', 2: '1'}
P = {('q0', '1'): ('1', 'R', 'q0'), ('q0', 'λ'): ('1', 'S', 'q0')}
pos, st, steps = 0, 'q0', 0
while True:
w, m, st2 = P[(st, tape.get(pos, 'λ'))]
tape[pos] = w
steps += 1
if m == 'S':
break
pos += 1 if m == 'R' else −1
st = st2
Типичные ошибки
- Сдвигают головку до записи символа.
- Не считают последний такт с командой S.
- Забывают, что пустая клетка таблицы означает невозможную пару «символ — состояние».
Что дальше
Проверьте себя на заданиях этого типа в тренажёре Upward. Начните с диагностики по предмету: она покажет, какие номера уже получаются, а какие стоит подтянуть, и по её итогам соберётся личный план подготовки.
Как это выглядит в задании 12
Пример 1 из 2
Программа: q0, «1» → 1, R, q0; q0, «λ» → 1, S, q0. Лента 111, головка на левой единице. Что на ленте после остановки и сколько тактов?
- Разбор
- Три такта по единицам и такт записи с остановкой; моделирование даёт 1111 и 4 такта.
- Ответ
- 1111; 4
Пример 2 из 2
Программа: q0, «1» → 0, R, q0; q0, «0» → 1, R, q0; q0, «λ» → λ, S, q0. Лента 1011, головка на первом символе. Результат?
- Разбор
- Каждый символ инвертируется, на пустой ячейке остановка: 0100, 5 тактов (проверено программой).
- Ответ
- 0100
Мини-тест: 5 вопросов
- Вопрос 1 из 5
Что означает команда 0, L, q3?
Показать ответ
Ответ: Записать 0, сдвинуться влево, перейти в q3.
Сдвиг после записи.
- Вопрос 2 из 5
Что означает S?
Показать ответ
Ответ: Остановку после текущей команды.
Такт засчитывается.
- Вопрос 3 из 5
В каком состоянии головка в начале?
Показать ответ
Ответ: q0.
Начальное состояние.
- Вопрос 4 из 5
Что такое a0?
Показать ответ
Ответ: Пустой символ.
Обычно λ.
- Вопрос 5 из 5
Что значит пустая клетка таблицы?
Показать ответ
Ответ: Пара «символ — состояние» невозможна.
Команды нет.
Проверьте всё задание 12, а не одну тему
Диагностика Upward покажет, какие задания ЕГЭ по информатике стоит подтянуть в первую очередь.
Уже есть аккаунт? Войти