Задание 12:
исполнитель МТ
Машина Тьюринга: лента из клеток, головка, таблица команд.
Решаем разбором таблицы: подписываем, что делает каждое состояние,
прогоняем ленту на коротком числе — и видим правило.
Базовый уровень, один балл. Ответ — одно целое число в десятичной записи.
условие
Как это выглядит на экзамене
На ленте в соседних ячейках записано двоичное представление числа
1000 без ведущих нулей, вокруг — пустые ячейки «λ». Головка
стоит в ближайшей ячейке справа от числа.
| λ | 0 | 1 |
|---|
| q0 | λ, L, q1 | | |
|---|
| q1 | 1, L, q2 | 0, L, q1 | 1, L, q1 |
|---|
| q2 | λ, S, q2 | | |
|---|
Определите результат. Ответ — в десятичной системе.
По форме демоверсии 2027, числа свои.
Что дано
Строка таблицы — состояние головки, столбец — символ под
ней. В клетке — команда: что записать, куда сдвинуться, в какое
состояние перейти.
Где теряют балл
Перепутали столбцы 0 и 1 (их порядок в шапке бывает разный), начали
не с той стороны, сдали двоичную запись вместо десятичной.
таблица
Как читать команду
- 1 — записать в текущую клетку 1 (может совпасть с тем, что
там было);
- L — шаг влево, R — вправо, S — остановка после
записи;
- q2 — новое состояние.
Работа начинается в q0. Пустая клетка «λ» — тоже
символ: команда в её столбце срабатывает за краем числа.
Порядок столбцов
Бывает λ, 0, 1, бывает λ, 1, 0 — в задачах экзаменов
встречаются оба. Каждый раз смотри в шапку.
Пустая клетка в таблице — пара «состояние — символ», которая не
встречается.
прогон
Лента по шагам: прибавить 1
| λ | 0 | 1 |
|---|
| q0 | λ, L, q1 | | |
|---|
| q1 | 1, R, q2 | 1, R, q2 | 0, L, q1 |
|---|
| q2 | λ, S, q2 | 0, R, q2 | 1, R, q2 |
|---|
Число 11 = 10112, головка справа. Рамка — головка, жёлтым —
изменённые клетки.
| начало, q0 | λ | 1 | 0 | 1 | 1 | λ |
| q1 | λ | 1 | 0 | 1 | 1 | λ |
| q1 | λ | 1 | 0 | 1 | 0 | λ |
| q1 | λ | 1 | 0 | 0 | 0 | λ |
| q2 | λ | 1 | 1 | 0 | 0 | λ |
| стоп | λ | 1 | 1 | 0 | 0 | λ |
1011 → 1100: 11 → 12. Состояние q1 единицы справа
делает нулями, первый 0 — единицей. Это и есть «+1».
формулы
Что бывает с числом
x — исходное число, n — сколько у него двоичных цифр.
| Программа | Результат | Пример: x = 1000, n = 10 |
|---|
дописала справа  (k цифр s) | x · 4 + 3 (x · 2k + s) | 4003 |
дописала слева  | x + 2n | 1000 + 1024 = 2024 |
дописала слева  | x + 2n+1 | 1000 + 2048 = 3048 |
| +1, потом дописала 1 | (x + 1) · 2 + 1 | 2003 |
| инверсия всех цифр | 2n − 1 − x | 1023 − 1000 = 23 |
| стёрла последнюю цифру | x // 2 | 500 |
Формула — для проверки: правило читается из таблицы, а прогон
ленты работает и там, где формулы нет.
стереть и поправить
Стирание и правка внутри числа
Стереть справа
Головка доходит до последней цифры и пишет λ — клетка
становится пустой. Бывает с условием: стёрла последнюю, следующую
стирает, только если там 0.
1097 = 10001001001 → стёрта 1 → последний 0 тоже
стёрт → 100010010 = 274.
Правка в начале
Головка уходит к началу числа, делает шаг вправо — на первую цифру —
и меняет одну цифру: первую 1 на «10», вторую слева 1 на 0, первый 0
на 1.
800 = 1100100000, вторая 1 → 0: 1000100000 = 544.
автомат
Состояния по кругу
Бывает программа, где 2–3 состояния по очереди переписывают каждую
клетку и идут в одну сторону. Тогда — таблица хода: клетка, что
было, в каком состоянии головка, что стало.
| клетка | 1 | 2 | 3 | 4 | 5 | 6 | 7 | … |
|---|
| было | 1 | 1 | 1 | 1 | 1 | 1 | 1 | … |
|---|
| состояние | q1 | q2 | q3 | q2 | q3 | q2 | q3 | … |
|---|
| стало | 1 | 0 | 1 | 0 | 1 | 0 | 1 | … |
|---|
После первой клетки повторяется блок из двух клеток «01». На ряду из 57
единиц: 1 клетка + 28 блоков. Нулей: 28 · 1 = 28.
Ряд из двух частей (сначала нули, потом единицы) считаем по
частям: вторая часть начинается в том состоянии, где кончилась первая.
обратная задача
Какое число было
Дан результат — найти исходное. Пойми правило и сними действия в
обратном порядке: убрать дописанные цифры, отменить инверсию или
«+1».
Программа дописала 1 слева и 111 справа; результат
3655 = 111001000111. Снимаем: 11001000 = 200.
Инверсия теряет длину
1001 и 01001 после инверсии дают одно и то же число: впереди нули не
видны. Исходных чисел много — с 4, 5, 6 … цифрами. Поэтому
спрашивают наименьшее или наибольшее, меньшее N.
демо 2026
Сколько нулей могло быть
Лента из L цифр, неизвестных. Программа «−1» идёт справа: нули хвоста
становятся единицами, ближайшая 1 — нулём, стоп.
| было |  | хвост — t нулей, A не меняется |
|---|
| стало |  | |
|---|
Пусть в A ровно z нулей. Нулей было z + t, стало z + 1.
Если стало ровно 343, то z = 342, а нулей было 342 + t — чем длиннее хвост,
тем больше. Хвост ограничен длиной: в A должно поместиться 342 нуля.
Перебрать ленты программой нельзя — их 2L. Только
рассуждением.
второй способ
Программой: выполнить таблицу
ловушки
Пять ловушек
- Шапка таблицы. Столбцы 0 и 1 стоят в разном порядке.
- Где головка. Слева или справа от числа — с этого края она и
начнёт.
- Пустая клетка — символ. Команды в столбце λ работают за краем
числа: там дописывают.
- Ответ в десятичной. Двоичную запись с ленты переведи.
- Ведущие нули. После инверсии или «−1» число может начинаться с
нуля — на значение это не влияет.
Страница практикума узнаёт эти ошибки по ответу и
называет, где именно сломалось.
практикум
Что дальше
Десять задач — по одной на каждую форму, все на экране сразу, порядок
свой. Ошибся — появится разбор: что делает каждое состояние и лента по
шагам, а кнопка «Новые числа» даст такую же задачу с другими числами.
| Что станет с числом | дописать справа · дописать слева · ±1 · инверсия · стереть справа · правка в начале · автомат |
|---|
| Посчитать цифры | сколько нулей или единиц после программы |
|---|
| Назад | какое число было · сколько нулей могло быть |
|---|
Исправленное не в зачёт: задача, решённая после разбора,
закрыта, но в отметку идёт новая — по кнопке «Новые числа». Добрать можно
хоть до пятёрки: 10 — «5», 9 — «4», 8 — «3».
дома
Домашняя работа
Те же десять форм, по одной задаче на каждую. Тип закрывается чистым
верным ответом; ошибся — придёт такая же задача с другими числами.
Как сдать
От восьми закрытых типов появится код работы вида
и кнопка «Сдать работу».
Вторая кнопка открывает письмо: к коду прикладываются снимки
черновика — подписанные состояния и лента до и после.
Зачем снимок
Число можно получить и не разобравшись. Черновик показывает, что
приём ваш, — поэтому он и просится вместе с ответом.
В начале следующей пары — проверочная из пяти
задач.
и 
, само в себя
и 
, само в себя
в себя · 
дальше
в себя · 
дальше
— одна клетка таблицы. Головка слева —
.
и перебрать 
. На экзамене таблица маленькая, и разбор
руками быстрее: программа — по желанию.