Задания для подготовки к ЕГЭ Машина Тьюринга
В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце – возможные состояния головки. На пересечении i-й строки и j-го столбца находится команда, которую выполняет МТ, когда головка обозревает j-й символ, находясь в i-м состоянии. Если пара «символ – состояние» невозможна, то клетка для команды остаётся пустой.
Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент – записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент – один из четырёх символов «L», «R», «N», «S». Символы «L» и «R» означают сдвиг в левую или правую ячейки соответственно, «N» – отсутствие сдвига, «S» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.
Например, команда 0, L, q3 выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние q3.
Выполните задание.
На ленте в соседних ячейках записано двоичное представление числа 77 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей слева к последовательности ячейке.
Программа работы исполнителя:
Определите результат работы программы. В ответе запишите получившееся на ленте число в десятичной системе счисления.
В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце – возможные состояния головки. На пересечении i-й строки и j-го столбца находится команда, которую выполняет МТ, когда головка обозревает j-й символ, находясь в i-м состоянии. Если пара «символ – состояние» невозможна, то клетка для команды остаётся пустой.
Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент – записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент – один из четырёх символов «L», «R», «N», «S». Символы «L» и «R» означают сдвиг в левую или правую ячейки соответственно, «N» – отсутствие сдвига, «S» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.
Например, команда 0, L, q3 выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние q3.
Выполните задание.
На ленте в соседних ячейках записана последовательность из 1000 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.
Программа работы исполнителя: 
После выполнения программы на ленте осталось ровно 789 нулей. Определите максимально возможное число нулей в исходной последовательности.
В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце – возможные состояния головки. На пересечении i-й строки и j-го столбца находится команда, которую выполняет МТ, когда головка обозревает j-й символ, находясь в i-м состоянии. Если пара «символ – состояние» невозможна, то клетка для команды остаётся пустой.
Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент – записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент – один из четырёх символов «L», «R», «N», «S». Символы «L» и «R» означают сдвиг в левую или правую ячейки соответственно, «N» – отсутствие сдвига, «S» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.
Например, команда 0, L, q3 выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние q3.
Выполните задание.
На ленте в соседних ячейках записано двоичное представление числа 2047 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей справа к последовательности ячейке.
Программа работы исполнителя:
Определите результат работы программы. В ответе запишите получившееся на ленте число в десятичной системе счисления.
На ленте в соседних ячейках записано двоичное представление числа 1234 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей слева от последовательности ячейке.
Программа работы исполнителя:
Определите результат работы программы. В ответе запишите получившееся на ленте число в десятичной системе счисления.
Памятка:
Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент – записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент – один из четырёх символов «L», «R», «N», «S». Символы «L» и «R» означают сдвиг в левую или правую ячейки соответственно, «N» – отсутствие сдвига, «S» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.
На ленте в соседних ячейках записано двоичное представление числа 2047 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.
Программа работы исполнителя:
Определите результат выполнения программы. В ответе запишите получившееся число в десятичной системе счисления.
Справка:
Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент – записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент – один из четырёх символов «L», «R», «N», «S». Символы «L» и «R» означают сдвиг в левую или правую ячейки соответственно, «N» – отсутствие сдвига, «S» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.
На ленте в соседних ячейках записана последовательность из 10000 символов в следующем порядке слева направо: сначала 2500 нулей, далее 2500 единиц, потом ещё раз 2500 нулей и затем 2500 единиц. Ячейки слева и справа от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности.
Программа работы исполнителя:
| λ | 0 | 1 | |
|---|---|---|---|
| q₀ | λ, R, q₁ | ||
| q₁ | 1, R, q₁ | 0, R, q₂ | |
| q₂ | 0, R, q₃ | 1, R, q₂ | |
| q₃ | λ, S, q₃ | 0, R, q₃ | 0, R, q₃ |
Определите количество единиц в последовательности, полученной после выполнения программы.
Справка: Символы «L» и «R» означают сдвиг в левую или правую ячейки соответственно, «N» – отсутствие сдвига, «S» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.
Например, команда 0, L, q3 выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние q3.
На ленте в соседних ячейках записана последовательность из 1000 символов, включающая только нули, единицы и двойки. Ячейки слева и справа от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности.
Программа работы исполнителя:
| λ | 0 | 1 | 2 | |
|---|---|---|---|---|
| q₀ | λ, R, q₁ | |||
| q₁ | λ, S, q₁ | 2, R, q₁ | 0, R, q₁ | 1, R, q₁ |
Известно, что в исходной строке находилось 333 единиц и 555 двоек. Определите сумму цифр в строке, получившейся после выполнения программы.
Справка: Символы «L» и «R» означают сдвиг в левую или правую ячейки соответственно, «N» – отсутствие сдвига, «S» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.
Например, команда 0, L, q3 выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние q3.
На ленте исполнителя МТ в соседних ячейках записано двоичное представление числа 23344113 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.
Программа работы исполнителя:
| λ | 1 | 0 | |
|---|---|---|---|
| q₀ | λ, L, q₁ | ||
| q₁ | λ,, S, q₁ | 0, L, q₁ | 1, L, q₁ |
Определите десятичное значение числа, записанного на ленте после работы программы.
Справка: Символы «L» и «R» означают сдвиг в левую или правую ячейки соответственно, «N» – отсутствие сдвига, «S» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.
Например, команда 0, L, q3 выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние q3.
На ленте исполнителя МТ в соседних ячейках записано двоичное представление числа 44 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.
Программа работы исполнителя:
| λ | 1 | 0 | |
|---|---|---|---|
| q₀ | λ, L, q₁ | ||
| q₁ | 1, S, q₁ | 0, L, q₁ | 1, S, q₁ |
Определите десятичное значение числа, записанного на ленте после работы программы.
Справка: Символы «L» и «R» означают сдвиг в левую или правую ячейки соответственно, «N» – отсутствие сдвига, «S» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.
Например, команда 0, L, q3 выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние q3.
На ленте в соседних ячейках записана последовательность из 1000 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.
Программа работы исполнителя:
| λ | 1 | 0 | |
|---|---|---|---|
| q₀ | λ, L, q₁ | ||
| q₁ | λ, S, q₁ | 0, S, q₁ | 1, L, q₁ |
После выполнения программы на ленте осталось ровно 67 нулей. Определите максимально возможное число нулей в исходной последовательности.
Справка: Символы «L» и «R» означают сдвиг в левую или правую ячейки соответственно, «N» – отсутствие сдвига, «S» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.
Например, команда 0, L, q3 выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние q3.
На ленте в соседних ячейках записана последовательность из 1000 символов в следующем порядке слева направо: сначала 7 единиц, далее 7 двоек, потом снова 7 единиц, потом снова 7 двоек и замыкает последовательность 972 нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в первой ячейке справа от последовательности.
Программа работы исполнителя:
| λ | 1 | 0 | 2 | |
|---|---|---|---|---|
| q₀ | λ, L, q₁ | |||
| q₁ | λ, S, q₁ | 0, S q₁ | 2, L, q₁ | 0, L, q₁ |
Определите, какое количество нулей осталось в последовательности после выполнения программы.
Справка: Символы «L» и «R» означают сдвиг в левую или правую ячейку соответственно, «N» – отсутствие сдвига, «S» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.
Например, команда 0, L, q3 выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние q3.
На ленте исполнителя МТ в соседних ячейках записана последовательность из 100 символов, включающая только нули, единицы и двойки. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности. Программа для исполнителя:
| λ | 0 | 1 | 2 | |
|---|---|---|---|---|
| q₀ | λ, L, q₁ | |||
| q₁ | λ, S, q₁ | 2, L, q₁ | 0, L, q₁ | 1, L, q₁ |
После выполнения программы получилась строка с количеством символов 1 втрое меньше символов 2, при этом сумма значений в ней равна 42. Сколько единиц было в исходной строке?
Справка: Символы «L» и «R» означают сдвиг в левую или правую ячейку соответственно, «N» – отсутствие сдвига, «S» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.
Например, команда 0, L, q3 выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние q3.
На ленте в соседних ячейках записана последовательность из 1000 символов в следующем порядке слева направо: сначала 1 единица, далее 5 двоек и замыкает последовательность 994 тройки. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в первой ячейке справа от последовательности.
Программа работы исполнителя:
| λ | 1 | 2 | 3 | |
|---|---|---|---|---|
| q₀ | λ, L, q₁ | |||
| q₁ | λ, S, q₁ | 3, L, q₁ | 1, N, q₂ | 2, L, q₁ |
| q₂ | 3, N, q₂ | 5, L, q₁ |
Определите, какое количество пятерок появилось в последовательности после выполнения программы.
Справка: Символы «L» и «R» означают сдвиг в левую или правую ячейку соответственно, «N» – отсутствие сдвига, «S» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.
Например, команда 0, L, q3 выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние q3.
На ленте в соседних ячейках записана последовательность из 1000 символов в следующем порядке слева направо: сначала 100 единиц, далее 800 двоек и замыкает последовательность 100 троек. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в первой ячейке справа от последовательности.
Программа работы исполнителя:
| λ | 1 | 2 | 3 | |
|---|---|---|---|---|
| q₀ | λ, L, q₁ | |||
| q₁ | λ, S, q₁ | 0, L, q₁ | 1, N, q₂ | 3, L, q₁ |
| q₂ | 3, L, q₁ |
Определите, какое количество троек осталось в последовательности после выполнения программы.
Справка: Символы «L» и «R» означают сдвиг в левую или правую ячейку соответственно, «N» – отсутствие сдвига, «S» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.
Например, команда 0, L, q3 выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние q3.
На ленте исполнителя МТ в соседних ячейках записана последовательность из 1575 символов, включающая только нули, единицы и двойки. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности. Программа для исполнителя:
| λ | 0 | 1 | 2 | |
|---|---|---|---|---|
| q₀ | λ, R, q₁ | |||
| q₁ | λ, S, q₁ | 4, R, q₁ | 0, R, q₁ | 0, R, q₁ |
После выполнения программы получилась строка с суммой значений в ней равна 252. Сколько двоек было в исходной строке, учитывая, что изначально количество двоек и единиц одинаково?
Справка: Символы «L» и «R» означают сдвиг в левую или правую ячейку соответственно, «N» – отсутствие сдвига, «S» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.
Например, команда 0, L, q3 выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние q3.
