Машина Тьюринга — головка над бесконечной лентой из ячеек: на каждом шаге она читает символ, записывает новый, сдвигается влево или вправо и меняет состояние по таблице-программе. Повышенный уровень: на ленте записано число, нужно выполнить программу и записать результат; ответ — число, 1 балл.
Ответ
число в поле ответа
Баллы
1 балл
Проверяет
умение выполнить алгоритм для исполнителя с фиксированным набором команд — машины Тьюринга, заданной таблицей
Сколько времени закладывать
около 6 минут по спецификации ФИПИ
Какие бывают подтипы
Выполнить программу машины Тьюринга — На ленте двоичная запись числа, программа задана таблицей «состояние — символ»: выполнить её и перевести результат в десятичную систему или посчитать число шагов до остановки.
Пример с полным разбором
Условие. На ленте машины Тьюринга записана двоичная запись числа 47 без ведущих нулей, остальные ячейки пустые (пустой символ — λ). Головка стоит в пустой ячейке сразу справа от числа, в состоянии q0. Команда «0, L, q1» означает: записать в ячейку 0, сдвинуться на одну ячейку влево и перейти в состояние q1; буква S вместо сдвига означает остановку. Выполните программу из таблицы и запишите получившееся число в десятичной системе.
λ
0
1
q0
λ, L, q1
q1
1, S, q1
1, S, q1
0, L, q1
47=1011112. Головка в состоянии q0 видит пустую ячейку: команда «λ, L, q1» оставляет λ, сдвигает головку на последнюю цифру числа и переводит её в q1.
В q1 на единице команда «0, L, q1»: единица становится нулём, головка идёт дальше влево. Так четыре последние единицы превращаются в нули.
Пятая цифра справа — 0. Команда «1, S, q1» записывает 1 и останавливает машину.
На ленте 1100002=48. Программа прибавляет к числу единицу: так же работает перенос разряда при сложении столбиком.
Ответ: 48
Частые ошибки
Сдвигают головку до записи символа, хотя команда сначала пишет символ, а потом сдвигает.
Берут команду только по символу, не глядя на состояние: пустая ячейка в q0 и в q1 — разные клетки таблицы.
Продолжают работу после команды с буквой S, хотя она останавливает машину.
Записывают в ответ двоичную запись вместо десятичного числа.
Путают, с какой стороны от числа стоит головка в начале.
Что нужно знать для задания 12
Оглавление курса «ЕГЭ по информатике» под это задание. Содержание открывается после оплаты.
Правила работы исполнителя подробно описаны в самом условии, с примером. Но быстро читать таблицу-программу стоит научиться заранее: по спецификации на задание отводится около 6 минут.
Что такое такт?
Одна выполненная команда: запись символа, сдвиг и смена состояния. Иногда спрашивают, сколько тактов проработает программа до остановки.