Открытый Банк заданий ЕГЭ по информатике, № 12 Машина Тьюринга, Задания на машину Тьюринга с ответами и решениями

Каталог заданий

Найдите нужные задания по ЕГЭ, Информатика, номеру или теме. Любое задание можно открыть в каталоге или решить в тренажёре.

Я готовлюсь к

Список задач

	$λ$	$1$	$0$
$q_0$	$λ, L, q_1$
$q_1$	$λ, S, q_1$	$0, S, q_1$	$1, L, q_1$

	$λ$	$1$	$0$
$q_0$	$λ, L, q_1$
$q_1$	$λ, S, q_1$	$0, L, q_1$	$1, L, q_1$

	$λ$	$1$	$0$
$q_0$	$λ, L, q_1$
$q_1$	$λ, S, q_1$	$0, S, q_1$	$1, L, q_1$

	$λ$	$2$	$1$	$0$
$q_0$	$λ, R, q_1$
$q_1$	$λ, S, q_1$	$1, R, q_1$	$2, R, q_1$	$2, R, q_1$

	$λ$	$1$	$0$
$q_0$	$λ, L, q_1$
$q_1$	$λ, S, q_1$	$0, L, q_1$	$1, L,q_1$

	$λ$	$1$	$0$
$q_0$	$λ, L, q_{1}$
$q_1$	$λ, S, q_{1}$	$0, S, q_{1}$	$1, L, q_{1}$

	$λ$	$1$	$0$
$q_0$	$λ, L, q_{1}$
$q_1$	$λ, S, q_{1}$	$0, L, q_{1}$	$1, S, q_{1}$

	$λ$	$1$	$0$
$q_0$	$λ, L, q_{1}$
$q_1$	$λ, S, q_{1}$	$0, L, q_{1}$	$1, L, q_{1}$

	$λ$	$1$	$0$
$q_0$	$λ, R, q_{1}$
$q_1$	$λ, S, q_{1}$	$0, R, q_{1}$	$1, R, q_{1}$

	$λ$	$1$	$0$
$q_0$	$λ, R, q_{1}$
$q_1$	$λ, S, q_{1}$	$0, R, q_{1}$	$1, S, q_{1}$

	$λ$	$2$	$1$	$0$
$q_0$	$λ, R, q_{1}$
$q_1$	$λ, S, q_{1}$	$0, R, q_{1}$	$2, R, q_{1}$	$1, R, q_{1}$

	$λ$	$2$	$1$	$0$
$q_0$	$λ, R, q_1$
$q_1$	$λ, S, q_{1}$	$0, R, q_{1}$	$2, R, q_{1}$	$1, R, q_{1}$

id 386361 балл

Задания на машину Тьюринга

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов $A=\{a_{0},a_{1},…,a_{n–1}\}$ ), включая специальный пустой символ $a_{0}$ .

Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний $Q=\{q_{0},q_{1},…,q_{n–1}\}$ . В начальный момент времени головка находится в начальном состоянии $q_{0}$ .

На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может переместиться в ячейку справа или слева от текущей, не меняя находящийся в ней символ, или заменить символ в текущей ячейке без сдвига в соседнюю ячейку. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии.

Программа работы исполнителя МТ задаётся в табличном виде.

	$a_{0}$	$a_{1}$	...
$q_{0}$	команда	команда	...
$q_{1}$	команда	команда	...
...	...	...	...

В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце – возможные состояния головки. На пересечении $i$ -й строки и $j$ -го столбца находится команда, которую выполняет МТ, когда головка обозревает $j$ -й символ, находясь в $i$ -м состоянии. Если пара «символ – состояние» невозможна, то клетка для команды остаётся пустой.

Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент – записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент – один из четырёх символов $«L»$ , $«R»$ , $«N»$ , $«S»$ . Символы $«L»$ и $«R»$ означают сдвиг в левую или правую ячейки соответственно, $«N»$ – отсутствие сдвига, $«S»$ – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.

Например, команда $0, L, q_{3}$ выполняется следующим образом: в текущую ячейку записывается символ $«0»$ , затем головка сдвигается в соседнюю слева ячейку и переходит в состояние $q_{3}$ .

Выполните задание

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

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

	$λ$	$0$	$1$
$q_{0}$	$λ, R, q_{1}$
$q_{1}$	$λ, L, q_{2}$	$0, R, q_{1}$	$1, R, q_1$
$q_{2}$		$λ, L, q_3$	$λ, L, q_3$
$q_3$		$λ, S, q_3$	$1, S, q_3$

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

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

id 398111 балл

Задания на машину Тьюринга

Программа работы исполнителя МТ задаётся в табличном виде.

	$a_{0}$	$a_{1}$	...
$q_{0}$	команда	команда	...
$q_{1}$	команда	команда	...
...	...	...	...

Выполните задание

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

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

	$λ$	$0$	$1$
$q_{0}$	$λ, L, q_{1}$
$q_{1}$	$1, R, q_{2}$	$1, R, q_{2}$	$0, L, q_{1}$
$q_{2}$	$1, S, q_{2}$	$0, R, q_{2}$	$1, R, q_{2}$

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

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

id 403781 балл

Задания на машину Тьюринга

Программа работы исполнителя МТ задаётся в табличном виде.

	$a_{0}$	$a_{1}$	...
$q_{0}$	команда	команда	...
$q_{1}$	команда	команда	...
...	...	...	...

Выполните задание

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

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

	$λ$	$0$	$1$
$q_{0}$	$λ, L, q_{1}$
$q_{1}$		$1, L, q_{1}$	$0, R, q_{2}$
$q_{2}$	$1, S, q_{2}$	$0, R, q_{2}$	$1, R, q_{2}$

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

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

id 403821 балл

Задания на машину Тьюринга

Программа работы исполнителя МТ задаётся в табличном виде.

	$a_{0}$	$a_{1}$	...
$q_{0}$	команда	команда	...
$q_{1}$	команда	команда	...
...	...	...	...

Выполните задание

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

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

	$λ$	$0$	$1$
$q_{0}$	$λ, L, q_{1}$
$q_{1}$	$λ, L, q_2$	$0, L, q_{1}$	$1, L, q_1$
$q_{2}$	$1, R, q_3$
$q_{3}$	$0, S, q_3$

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

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

id 403871 балл

Задания на машину Тьюринга

Программа работы исполнителя МТ задаётся в табличном виде.

	$a_{0}$	$a_{1}$	...
$q_{0}$	команда	команда	...
$q_{1}$	команда	команда	...
...	...	...	...

Выполните задание

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

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

	$λ$	$0$	$1$
$q_{0}$	$λ, L, q_{1}$
$q_{1}$	$λ, R, q_2$	$0, L, q_1$	$1, L, q_1$
$q_{2}$			$0, L, q_3$
$q_3$	$1, S, q_3$

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

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

id 403881 балл
Задания на машину Тьюринга
Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов $A=\{a_{0},a_{1},…,a_{n–1}\}$ ), включая специальный пустой символ $a_{0}$ .
Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний $Q=\{q_{0},q_{1},…,q_{n–1}\}$ . В начальный момент времени головка находится в начальном состоянии $q_{0}$ .
На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может переместиться в ячейку справа или слева от текущей, не меняя находящийся в ней символ, или заменить символ в текущей ячейке без сдвига в соседнюю ячейку. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии.
Программа работы исполнителя МТ задаётся в табличном виде.
$a_{0}$
$a_{1}$
...
$q_{0}$
команда
команда
...
$q_{1}$
команда
команда
...
...
...
...
...
В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце – возможные состояния головки. На пересечении $i$ -й строки и $j$ -го столбца находится команда, которую выполняет МТ, когда головка обозревает $j$ -й символ, находясь в $i$ -м состоянии. Если пара «символ – состояние» невозможна, то клетка для команды остаётся пустой.
Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент – записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент – один из четырёх символов $«L»$ , $«R»$ , $«N»$ , $«S»$ . Символы $«L»$ и $«R»$ означают сдвиг в левую или правую ячейки соответственно, $«N»$ – отсутствие сдвига, $«S»$ – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.
Например, команда $0, L, q_{3}$ выполняется следующим образом: в текущую ячейку записывается символ $«0»$ , затем головка сдвигается в соседнюю слева ячейку и переходит в состояние $q_{3}$ .
Выполните задание
На ленте в соседних ячейках записано двоичное представление числа 1023 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами $«λ»$ . В начальный момент времени головка расположена в ближайшей справа к последовательности ячейке.
Программа работы исполнителя:
$λ$
$0$
$1$
$q_{0}$
$λ, L, q_{1}$
$q_{1}$
$1, L, q_2$
$1, S, q_2$
$0, L, q_1$
$q_{2}$
$λ, S, q_{2}$
Определите результат выполнения программы.
В ответе запишите получившееся число в десятичной системе счисления.

id 830281 балл

Задания на машину Тьюринга

Программа работы исполнителя МТ задаётся в табличном виде.

	$a_{0}$	$a_{1}$	...
$q_{0}$	команда	команда	...
$q_{1}$	команда	команда	...
...	...	...	...

Выполните задание

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

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

	$λ$	$0$	$1$
$q_{0}$	$λ, R, q_{1}$
$q_{1}$	$0, R, q_2$	$0, R, q_1$	$1, R, q_1$
$q_{2}$	$0, R, q_3$
$q_3$	$λ, S, q_3$

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

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

id 830291 балл
Задания на машину Тьюринга
Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов $A=\{a_{0},a_{1},…,a_{n–1}\}$ ), включая специальный пустой символ $a_{0}$ .
Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний $Q=\{q_{0},q_{1},…,q_{n–1}\}$ . В начальный момент времени головка находится в начальном состоянии $q_{0}$ .
На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может переместиться в ячейку справа или слева от текущей, не меняя находящийся в ней символ, или заменить символ в текущей ячейке без сдвига в соседнюю ячейку. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии.
Программа работы исполнителя МТ задаётся в табличном виде.
$a_{0}$
$a_{1}$
...
$q_{0}$
команда
команда
...
$q_{1}$
команда
команда
...
...
...
...
...
В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце – возможные состояния головки. На пересечении $i$ -й строки и $j$ -го столбца находится команда, которую выполняет МТ, когда головка обозревает $j$ -й символ, находясь в $i$ -м состоянии. Если пара «символ – состояние» невозможна, то клетка для команды остаётся пустой.
Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент – записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент – один из четырёх символов $«L»$ , $«R»$ , $«N»$ , $«S»$ . Символы $«L»$ и $«R»$ означают сдвиг в левую или правую ячейки соответственно, $«N»$ – отсутствие сдвига, $«S»$ – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.
Например, команда $0, L, q_{3}$ выполняется следующим образом: в текущую ячейку записывается символ $«0»$ , затем головка сдвигается в соседнюю слева ячейку и переходит в состояние $q_{3}$ .
Выполните задание
На ленте в соседних ячейках записано двоичное представление числа 2047 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами $«λ»$ . В начальный момент времени головка расположена в ближайшей справа к последовательности ячейке.
Программа работы исполнителя:
$λ$
$0$
$1$
$q_{0}$
$λ, L, q_{1}$
$q_{1}$
$1, L, q_2$
$1, S, q_1$
$0, L, q_1$
$q_{2}$
$λ, S, q_2$
Определите результат выполнения программы.
В ответе запишите получившееся число в десятичной системе счисления.

id 830301 балл

Задания на машину Тьюринга

Программа работы исполнителя МТ задаётся в табличном виде.

	$a_{0}$	$a_{1}$	...
$q_{0}$	команда	команда	...
$q_{1}$	команда	команда	...
...	...	...	...

Выполните задание

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

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

	$λ$	$0$	$1$
$q_{0}$	$λ, L, q_{1}$
$q_{1}$	$λ, R, q_2$	$0, L, q_1$	$1, L, q_1$
$q_{2}$		$0, R, q_2$	$1, R, q_3$
$q_3$	$λ, R, q_4$	$0, R, q_3$	$0, R, q_4$
$q_4$	$λ, S, q_4$	$0, R, q_4$	$1, R, q_4$

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

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

id 830311 балл

Задания на машину Тьюринга

Программа работы исполнителя МТ задаётся в табличном виде.

	$a_{0}$	$a_{1}$	...
$q_{0}$	команда	команда	...
$q_{1}$	команда	команда	...
...	...	...	...

Выполните задание

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

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

	$λ$	$0$	$1$
$q_{0}$	$1, R, q_{1}$
$q_{1}$	$1, R, q_2$	$1, R, q_1$	$0, R, q_1$
$q_{2}$	$1, R, q_3$
$q_3$	$0, S, q_3$

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

id 830321 балл

Задания на машину Тьюринга

Программа работы исполнителя МТ задаётся в табличном виде.

	$a_{0}$	$a_{1}$	...
$q_{0}$	команда	команда	...
$q_{1}$	команда	команда	...
...	...	...	...

Выполните задание

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

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

	$λ$	$1$	$0$
$q_0$	$1, R, q_1$
$q_1$	$1, R, q_2$	$0, R, q_1$	$1, R, q_1$
$q_2$	$1, R, q_3$
$q_3$	$1, S, q_3$

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

id 830331 балл

Задания на машину Тьюринга

Программа работы исполнителя МТ задаётся в табличном виде.

	$a_{0}$	$a_{1}$	...
$q_{0}$	команда	команда	...
$q_{1}$	команда	команда	...
...	...	...	...

Выполните задание

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

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

	$λ$	$0$	$1$
$q_0$	$λ, R, q_1$
$q_1$	$1, R, q_2$	$1, R, q_1$	$0, R, q_1$
$q_2$	$0, R, q_3$
$q_3$	$λ, S, q_3$

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

Основная информация об экзамене

Когда будет экзамен

ИЮНЬ 2027

Дата сдачи 2027

18 ИЮНЯ

Резервные даты 2027

24 И 25 ИЮНЯ

Экзамен длится

3 Ч 55 МИН

Результаты выпускников 2025 года

Изучай средние баллы и оценивай свои шансы

55.8Среднийбалл 2025

800Стобалльниковв 2025

11%

0–30

25.2%

31–50

28.1%

51–70

20.7%

71–85

15%

86–100

Ниже порога 40БВыше порога

Банк заданий
ЕГЭ по информатике Задание №12 Машина Тьюринга, Задания на машину Тьюринга

Каталог заданий

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Основная информация об экзамене

Результаты выпускников 2025 года

Твой путь к высоким баллам начинается здесь

Выбирай предмети начинай подготовку

ХОЧЕШЬ ПОСТУПИТЬ НА БЮДЖЕТ?

Банк заданий ЕГЭ по информатике Задание №12 Машина Тьюринга, Задания на машину Тьюринга

Каталог заданий

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Задания на машину Тьюринга

Основная информация об экзамене

Результаты выпускников 2025 года

Твой путь к высоким баллам начинается здесь

Выбирай предмети начинай подготовку

ХОЧЕШЬ ПОСТУПИТЬ НА БЮДЖЕТ?

Банк заданий
ЕГЭ по информатике Задание №12 Машина Тьюринга, Задания на машину Тьюринга