На ленте в соседних ячейках было записано двоичное представление некоторого целого положительного числа \(N\) без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами \(\lambda\). В начальный момент времени головка располагалась в ближайшей ячейке слева от последовательности. Над лентой выполнили приведённую ниже программу для машины Тьюринга.
После завершения работы программы на ленте оказалось двоичное представление числа \(M = 27\) (без ведущих нулей).
Начальное состояние — \(q_1\).
Программа работы исполнителя:
| |
\(\lambda\) |
\(0\) |
\(1\) |
| \(q_1\) |
\(\lambda, R, q_2\) |
|
|
| \(q_2\) |
\(\lambda, L, q_3\) |
\(0, R, q_2\) |
\(1, R, q_2\) |
| \(q_3\) |
|
\(\lambda, L, q_4\) |
\(\lambda, L, q_4\) |
| \(q_4\) |
|
\(\lambda, S, q_4\) |
\(\lambda, S, q_4\) |
Какое наибольшее количество единиц могло содержаться в двоичной записи исходного числа \(N\)? В ответе укажите количество.