Машина Тьюринга

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

После выполнения программы на ленте осталось 125 нулей. Определите максимально возможное число нулей в исходной последовательности.

На ленте в соседних ячейках записана последовательность из 333 символов, среди которых могут быть только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами λ. В начальный момент времени головка расположена в ближайшей справа к последовательности ячейке. Программа работы исполнителя:

После выполнения программы на ленте осталось 120 нулей. Определите максимально возможное число нулей в исходной последовательности.

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

После выполнения программы на ленте осталось 125 нулей. Определите минимально возможное число нулей в исходной последовательности.

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

После выполнения программы на ленте осталось 137 нулей. Определите минимально возможное число нулей в исходной последовательности.

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

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

После выполнения программы на ленте осталось ровно 125 нулей. Определите число нулей в исходной последовательности.

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

После выполнения программы на ленте осталось ровно 100 нулей. Определите число нулей в исходной последовательности.

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

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

После выполнения программы на ленте осталось 125 нулей. Определите минимально возможное число нулей в исходной последовательности.

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

После выполнения программы на ленте осталось ровно 100 нулей. Определите минимально возможное число нулей в исходной последовательности.

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

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

После выполнения программы на ленте осталось ровно 50 нулей. Определите максимально возможное число нулей в исходной последовательности.

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

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

После выполнения программы на ленте осталось ровно 100 нулей. Определите максимально возможное число нулей в исходной последовательности.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

И опять у АвтоВАЗа проблемы: на конвейере заклинило станок гравировки VIN-номеров, и теперь головка ездит по табличке туда-сюда, выбивая вместо номера непонятно что. На ленте в соседних ячейках записано двоичное представление числа $14$ без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами <>. В начальный момент времени головка расположена в ближайшей справа к последовательности ячейке.

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

$$\begin{array}{|c|c|c|c|} \hline & \lambda & 1 & 0 \\ \hline q_0 & \lambda,\,L,\,q_1 & & \\ \hline q_1 & & 1,\,L,\,q_2 & 0,\,L,\,q_3 \\ \hline q_2 & \lambda,\,S,\,q_3 & 0,\,L,\,q_3 & 1,\,L,\,q_2 \\ \hline q_3 & \lambda,\,S,\,q_3 & 1,\,L,\,q_2 & 0,\,L,\,q_3 \\ \hline \end{array}$$

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

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

После выполнения программы на ленте оказалась двоичная запись числа 240. Определите десятичное значение наименьшего числа, которое могло быть записано на ленте до начала работы программы.

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

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

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

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

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя

$$A = \{a_0, a_1, ..., a_{n-1}\},$$

включая специальный пустой символ $\lambda$.

В начальный момент времени головка находится в начальном состоянии $q_0$.

На ленте в соседних ячейках записано двоичное представление числа $1097$ без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами $\lambda$. В начальный момент времени головка расположена в ближайшей слева к последовательности ячейке.

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

$$\begin{array}{|c|c|c|c|} \hline & \lambda & 0 & 1 \\ \hline q_0 & \lambda, R, q_1 & & \\ \hline q_1 & \lambda, L, q_2 & 0, R, q_1 & 1, R, q_1 \\ \hline q_2 & & \lambda, L, q_3 & \lambda, L, q_3 \\ \hline q_3 & & \lambda, S, q_3 & \lambda, S, q_3 \\ \hline \end{array}$$

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

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя

$$A = \{a_0, a_1, ..., a_{n-1}\},$$

включая специальный пустой символ $\lambda$.

В начальный момент времени головка находится в начальном состоянии $q_0$.

На ленте в соседних ячейках записано двоичное представление числа $1097$ без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами $\lambda$. В начальный момент времени головка расположена в ближайшей слева к последовательности ячейке.

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

$$\begin{array}{|c|c|c|c|} \hline & \lambda & 0 & 1 \\ \hline q_0 & \lambda, R, q_1 & & \\ \hline q_1 & \lambda, L, q_2 & 0, R, q_1 & 1, R, q_1 \\ \hline q_2 & & \lambda, L, q_3 & \lambda, L, q_3 \\ \hline q_3 & & \lambda, S, q_3 & \lambda, S, q_3 \\ \hline \end{array}$$

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

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

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

$$\begin{array}{|c|c|c|c|} \hline & \lambda & 0 & 1 \\ \hline q_0 & \lambda,\,L,\,q_1 & & \\ \hline q_1 & \lambda,\,R,\,q_2 & 0,\,L,\,q_1 & 1,\,L,\,q_1 \\ \hline q_2 & & & 0,\,L,\,q_3 \\ \hline q_3 & 1,\,S,\,q_3 & & \\ \hline \end{array}$$

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