Машина Тьюринга — головка над бесконечной лентой из ячеек: на каждом шаге она читает символ, записывает новый, сдвигается влево или вправо и меняет состояние по таблице-программе. Повышенный уровень: на ленте записано число, нужно выполнить программу и записать результат; ответ — число, 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 |
Ответ: 48
Условие.
На ленте машины Тьюринга (исполнителя МТ) записано число 834 в двоичной системе без ведущих нулей, по одной цифре в ячейке; во всех остальных ячейках стоит пустой символ λ. Головка в состоянии q0 стоит на первой пустой ячейке справа от записи числа.
λ 0 1
q0 λ, L, q1
q1 λ, S, q1 λ, S, q1
Какое число окажется записано на ленте после остановки исполнителя? Ответ дайте в десятичной системе счисления.
Решение.
Двоичная запись числа 834 — 10 разрядов.
Последний разряд стёрт: вместо него в ячейке пустой символ.
Стереть младший двоичный разряд — то же самое, что разделить число на 2 нацело.
Ответ: 417
Условие.
На ленте машины Тьюринга (исполнителя МТ) записано число 845 в двоичной системе без ведущих нулей, по одной цифре в ячейке; во всех остальных ячейках стоит пустой символ λ. Головка в состоянии q0 стоит на первой пустой ячейке справа от записи числа.
λ 0 1
q0 λ, L, q1
q1 λ, S, q1 λ, S, q1
Какое число окажется записано на ленте после остановки исполнителя? Ответ дайте в десятичной системе счисления.
Решение.
Двоичная запись числа 845 — 10 разрядов.
Последний разряд стёрт: вместо него в ячейке пустой символ.
Стереть младший двоичный разряд — то же самое, что разделить число на 2 нацело.
Ответ: 422
Условие.
На ленте машины Тьюринга (исполнителя МТ) записано число 393 в двоичной системе без ведущих нулей, по одной цифре в ячейке; во всех остальных ячейках стоит пустой символ λ. Головка в состоянии q0 стоит на первой пустой ячейке справа от записи числа.
λ 0 1
q0 λ, L, q1
q1 λ, S, q1 λ, S, q1
Какое число окажется записано на ленте после остановки исполнителя? Ответ дайте в десятичной системе счисления.
Решение.
Двоичная запись числа 393 — 9 разрядов.
Последний разряд стёрт: вместо него в ячейке пустой символ.
Стереть младший двоичный разряд — то же самое, что разделить число на 2 нацело.
Ответ: 196
Оглавление курса «ЕГЭ по информатике» под это задание. Содержание открывается после оплаты.