На ленте в соседних ячейках записано двоичное представление целого положительного числа без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «д». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности. Программа работы исполнителя: 1 0 12240 λ qo λ, L, q q λ, S, q1 0, L, qı 1, L, qı 011110000 до работи После выполнения программы на ленте оказалась двоичная запись числа 240. Определите десятичное значение наименьшего числа, которое могло быть записано на ленте до начала работы программы. Задание 13 120

Ответ: 120

Для решения этой задачи необходимо понять, какие преобразования выполняет программа и как эти преобразования влияют на число, записанное на ленте.

• Программа заменяет все символы λ на 1, то есть все пустые ячейки заменяются единицами.
• Она также сдвигает головку влево, пока не встретит первый символ, отличный от 1.
• После выполнения программы на ленте остается двоичная запись числа 240.
• Число 240 в двоичном виде: 011110000.
• Чтобы определить наименьшее число, которое могло быть записано на ленте до начала работы программы, нам нужно учесть, что программа могла заменить несколько символов λ на 1.

Логика такая:

• Если до начала работы программы на ленте было записано число, меньшее 240, то программа должна была заменить какие-то символы λ на 1.
• Наименьшее возможное число получится, если мы заменим все нули в двоичной записи числа 240 на λ, а затем программа заменит их на 1.
• Однако, нам нужно найти наименьшее число, которое могло быть на ленте до начала работы программы. Это означает, что мы должны оставить как можно больше нулей в двоичной записи числа 240.

Двоичное представление числа 240: 011110000.

Теперь определим, какое наименьшее число могло быть на ленте до начала работы программы. Заменим один из нулей на λ:

λ11110000. Это будет соответствовать числу 128 + 64 + 32 + 16 = 240.

Если бы мы заменили больше нулей на λ, то число было бы еще меньше.

Далее нам нужно заменить λ на 0, так как программа заменит все λ на 1. Но нам нужно найти наименьшее число, которое могло быть на ленте до начала работы программы.

Наименьшее число, которое могло быть на ленте до начала работы программы, это когда мы заменяем первый ноль на λ, а все остальные нули оставляем нулями.

Итак, λ11110000. Это число равно 128 + 64 + 32 + 16 = 240.

Теперь мы заменим λ на 0. 011110000. Это число равно 128 + 64 + 32 + 16 = 240.

Теперь мы заменим λ на 1. 11110000. Это число равно 128 + 64 + 32 + 16 + 128 = 240.

Наименьшее число, которое могло быть на ленте до начала работы программы, это число, которое получается, если мы заменим последний ноль на λ.

01111000λ. Это число равно 128 + 64 + 32 + 16 + 0 + 0 + 0 + 0 = 240.

Если бы у нас было число 01110111, то тогда программа могла бы заменить какие-то символы λ на 1 и получить число 240.

Минимальное число, которое программа могла заменить на 240, это число, которое меньше 240 на 1.

Теперь определим наименьшее число, которое могло быть на ленте до начала работы программы.

Наименьшее число это 120

Ответ: 120