Фотография
нажмите — покажем
нажмите — покажем
Решение для Задания 12
183 в двоичной системе: 10110111.
Лента: …λ λ 1 0 1 1 0 1 1 1 λ… (головка на выделенном λ, состояние q0).
Алгоритм работает в два этапа:
q0: головка читает λ, пишет λ, сдвигается вправо, переходит в q1.
q1: головка движется вправо, не меняя символы (0 → 0, 1 → 1), пока не встретит λ справа от числа. При встрече λ сдвигается влево и переходит в q2.
q2: головка движется влево, прибавляя 1 к числу: 1 → 0 с переносом (движение влево), 0 → 1 без переноса (стоп, q3). Если встречает λ слева от числа — пишет 1 (перенос за левый край) и останавливается.
Трассировка для 10110111 (три единицы на конце — три переноса) - см. изображение.
На ленте: 1 0 1 1 1 0 0 0 = 10111000 = 184.
Ответ: 184
93 ·