4 Метод — пошаговая трассировка

Метод — пошаговая трассировка

Надёжнее всего вести таблицу шагов: на каждом шаге фиксируем состояние, символ под кареткой и что получилось. Так ничего не потеряешь.

1. Прочитай условие и выпиши программу-таблицу.

2. Разберись, что делает машина, на маленьком примере (2–3 символа).

3. Веди пошаговую запись: состояние → символ → действие → новая лента.

4. Дойди до команды стоп и запиши результат.

5. Если спрашивают про исходные данные — рассуждай от результата назад.

Пример: разбор по шагам

Условие

На ленте записано число 1023 в двоичной системе (это десять единиц подряд: 1111111111), остальное — λ. Каретка стоит на пустой ячейке справа от числа в состоянии q₀. Программа: перейти к числу, заменить каждую единицу на 0, а слева дописать единицу. Что получится в десятичной системе?

Прослеживаем работу:

Шаг

Что делает машина

Лента

старт

1023 = десять единиц, каретка справа на λ

1111111111

сдвиг влево

команда λ, L, q₁ — встаём на последнюю единицу

1111111111

проход по единицам

в q₁ каждую 1 меняем на 0 и идём влево (0, L, q₁)

0000000000

слева пусто

дошли до λ слева — пишем 1 (1, L, q₂)

10000000000

стоп

команда λ, S — останавливаемся

10000000000

Итоговая запись 10000000000₂ в десятичной системе — это 1024.

Ответ: 1024

Проверка по смыслу: 1023 = 2¹⁰ − 1 (десять единиц), а после обработки получилось 2¹⁰ = 1024.