№610402159

Исполнитель МТ - это головка, которая читает и записывает символы на бесконечной ленте, разделённой на ячейки. В каждой ячейке записан ровно один символ алфавита; символ «λ» обозначает пустую ячейку. Головка находится в одном из состояний q₀, q₁, …; в начальный момент - в состоянии q₀.

Программа задана таблицей. Строка таблицы - состояние головки, столбец - символ в текущей ячейке; в клетке указана команда «записываемый символ, движение, новое состояние». Сначала в текущую ячейку записывается указанный символ, затем головка сдвигается: L - на одну ячейку влево, R - на одну ячейку вправо, N - остаётся на месте, а S - работа исполнителя завершается (головка остаётся на месте). После сдвига головка переходит в новое состояние. Пустая клетка таблицы означает, что такая комбинация не встречается.

Алфавит исполнителя: λ, 0, 1. На ленте в соседних ячейках записано двоичное представление некоторого натурального числа N без ведущих нулей; остальные ячейки пусты. В начальный момент головка расположена в ближайшей ячейке справа от последовательности.

Программа исполнителя:

Определите наименьшее натуральное число N, при котором после выполнения программы на ленте окажется двоичная запись числа 123985.