Решение: Работа машины Тьюринга
На ленте в соседних ячейках записано двоичное представление числа 2025 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей справа к последовательности ячейке. Выполните программу работы исполнителя и определите результат в десятичной системе счисления.
| Состояние / символ | λ | 0 | 1 |
|---|---|---|---|
| q_0 | λ, L, q_1 | ||
| q_1 | λ, R, q_2 | 0, L, q_1 | 1, L, q_1 |
| q_2 | 0, L, q_3 | ||
| q_3 | 1, S, q_3 |
Решение по шагам
6 шаговПредставим число 2025 в двоичной системе счисления.
$$2025_{10}=11111101001_2$$В состоянии q_0 головка из ближайшей справа пустой ячейки перемещается влево и переходит в состояние q_1.
В состоянии q_1 головка движется влево по всем разрядам числа, не изменяя их. Достигнув пустой ячейки слева от числа, она переходит вправо в состояние q_2.
В состоянии q_2 головка попадает на первый разряд числа, равный 1, заменяет его на 0 и перемещается влево, в состояние q_3.
В состоянии q_3 в пустую ячейку слева записывается 1, после чего работа завершается. Получается двоичная запись $101111101001_2$.
Переведём получившееся число в десятичную систему.
$$101111101001_2=2^{11}+2^9+2^8+2^7+2^6+2^4+2^3+2^0=3049$$Где здесь ошибаются
Не учитывать, что состояние q_2 заменяет первый разряд числа 1 на 0.
Забыть про запись единицы в пустую ячейку слева в состоянии q_3.
Перевести в десятичную систему исходную запись 2025 вместо результата работы программы.