Question

На ленте в соседних ячейках записано двоичное представление числа 1023 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей справа к последовательности ячейке.

Программа работы исполнителя МТ:

| | λ | 0 | 1 |
|---|---|---|---|
| $q_0$ | λ, L, $q_1$ | | |
| $q_1$ | 1, L, $q_2$ | 1, S, $q_2$ | 0, L, $q_1$ |

Определите результат выполнения программы. В ответе запишите получившееся число в десятичной системе счисления.

![Рисунок](https://ege.sdamgia.ru/formula/svg/0a/0a8dd345cc8e328e7fa8081b668d97e9.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/36/36b6f2f251e363add6d381cd113f3c02.svg)

Accepted Answer

1024

Answer

Идея решения: программа преобразует двоичное число путём замены последовательности единиц на нули и добавления единицы слева, что эквивалентно прибавлению 1 к исходному числу.

Двоичное представление числа 1023: $1023_{10} = 1111111111_2$ (десять единиц).

Начальное состояние ленты:
```
... λ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | λ ...
                                                    ↑ (головка здесь)
```

Выполнение программы:

1. Головка в состоянии $q_0$, обозревает λ. Команда: λ, L, $q_1$ — записать λ, сдвинуться влево, перейти в $q_1$.

2. Головка в состоянии $q_1$, обозревает последний символ 1. Команда: 0, L, $q_1$ — записать 0, сдвинуться влево, остаться в $q_1$.

3. Программа продолжает заменять каждый встреченный символ 1 на 0 и двигаться влево, пока не встретит символ 0 или λ.

4. После замены всех десяти единиц на нули головка обозревает λ (слева от последовательности). Команда: 1, L, $q_2$ — записать 1, сдвинуться влево, перейти в $q_2$.

5. В состоянии $q_2$ программа останавливается (команда S).

Результирующая лента:
```
... λ | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | λ ...
```

Двоичное число: $10000000000_2 = 1024_{10}$.

Задание №12Алгоритмы и исполнителиЕГЭ по информатике