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

Бесплатно готовься к экзаменам
на проверенных материалах ФИПИ

Банк заданий ЕГЭ по информатике от 100балльного репетитора

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

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

Я готовлюсь к
Номер задания
Тема
Список задач
  • id 137221 балл

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

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

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

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

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

    a0a_{0}

    a1a_{1}

    ...

    q0q_{0}

    команда

    команда

    ...

    q1q_{1}

    команда

    команда

    ...

    ...

    ...

    ...

    ...

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

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

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

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

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

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

     

    λλ

    11

    00

    q0q_0

    λ,L,q1λ, L, q_1

     

     

    q1q_1

    λ,S,q1λ, S, q_1

    0,S,q10, S, q_1

    1,L,q11, L, q_1

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

  • id 137781 балл

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

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

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

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

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

    a0a_{0}

    a1a_{1}

    ...

    q0q_{0}

    команда

    команда

    ...

    q1q_{1}

    команда

    команда

    ...

    ...

    ...

    ...

    ...

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

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

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

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

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

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

     

    λλ

    11

    00

    q0q_0

    λ,L,q1λ, L, q_1

     

     

    q1q_1

    λ,S,q1λ, S, q_1

    0,L,q10, L, q_1

    1,L,q11, L, q_1

    После выполнения программы единиц на ленте стало в девять раз больше, чем нулей. Сколько единиц содержалось в исходной последовательности?

  • id 6371 балл

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

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

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

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

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

    a0a_{0}

    a1a_{1}

    ...

    q0q_{0}

    команда

    команда

    ...

    q1q_{1}

    команда

    команда

    ...

    ...

    ...

    ...

    ...

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

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

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

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

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

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

     

    λλ

    11

    00

    q0q_0

    λ,L,q1λ, L, q_1

     

     

    q1q_1

    λ,S,q1λ, S, q_1

    0,S,q10, S, q_1

    1,L,q11, L, q_1

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

  • id 6661 балл

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

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

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

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

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

    a0a_{0}

    a1a_{1}

    ...

    q0q_{0}

    команда

    команда

    ...

    q1q_{1}

    команда

    команда

    ...

    ...

    ...

    ...

    ...

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

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

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

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

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

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

     

    λλ

    22

    11

    00

    q0q_0

    λ,R,q1λ, R, q_1

     

     

     

    q1q_1

    λ,S,q1λ, S, q_1

    1,R,q11, R, q_1

    2,R,q12, R, q_1

    2,R,q12, R, q_1

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

  • id 7721 балл

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

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

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

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

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

    a0a_{0}

    a1a_{1}

    ...

    q0q_{0}

    команда

    команда

    ...

    q1q_{1}

    команда

    команда

    ...

    ...

    ...

    ...

    ...

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

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

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

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

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

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

     

    λλ

    11

    00

    q0q_0

    λ,L,q1λ, L, q_1

     

     

    q1q_1

    λ,S,q1λ, S, q_1

    0,L,q10, L, q_1

    1,L,q11, L,q_1

    После выполнения программы единиц на ленте стало в 4 раза больше, чем нулей. Сколько единиц содержалось в исходной последовательности?

  • id 8651 балл

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

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

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

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

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

    a0a_{0}

    a1a_{1}

    ...

    q0q_{0}

    команда

    команда

    ...

    q1q_{1}

    команда

    команда

    ...

    ...

    ...

    ...

    ...

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

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

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

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

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

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

     

    λλ

    11

    00

    q0q_0

    λ,L,q1λ, L, q_{1}

     

     

    q1q_1

    λ,S,q1λ, S, q_{1}

    0,S,q10, S, q_{1}

    1,L,q11, L, q_{1}

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

  • id 9861 балл

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

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

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

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

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

    a0a_{0}

    a1a_{1}

    ...

    q0q_{0}

    команда

    команда

    ...

    q1q_{1}

    команда

    команда

    ...

    ...

    ...

    ...

    ...

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

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

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

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

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

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

     

    λλ

    11

    00

    q0q_0

    λ,L,q1λ, L, q_{1}

     

     

    q1q_1

    λ,S,q1λ, S, q_{1}

    0,L,q10, L, q_{1}

    1,S,q11, S, q_{1}

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

  • id 16481 балл

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

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

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

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

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

    a0a_{0}

    a1a_{1}

    ...

    q0q_{0}

    команда

    команда

    ...

    q1q_{1}

    команда

    команда

    ...

    ...

    ...

    ...

    ...

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

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

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

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

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

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

     

    λλ

    11

    00

    q0q_0

    λ,L,q1λ, L, q_{1}

     

     

    q1q_1

    λ,S,q1λ, S, q_{1}

    0,L,q10, L, q_{1}

    1,L,q11, L, q_{1}

    После выполнения программы единиц на ленте стало в три раза больше, чем нулей. Сколько единиц содержалось в исходной последовательности?

  • id 17451 балл

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

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

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

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

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

    a0a_{0}

    a1a_{1}

    ...

    q0q_{0}

    команда

    команда

    ...

    q1q_{1}

    команда

    команда

    ...

    ...

    ...

    ...

    ...

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

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

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

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

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

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

     

    λλ

    11

    00

    q0q_0

    λ,R,q1λ, R, q_{1}

     

     

    q1q_1

    λ,S,q1λ, S, q_{1}

    0,R,q10, R, q_{1}

    1,R,q11, R, q_{1}

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

  • id 137971 балл

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

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

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

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

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

    a0a_{0}

    a1a_{1}

    ...

    q0q_{0}

    команда

    команда

    ...

    q1q_{1}

    команда

    команда

    ...

    ...

    ...

    ...

    ...

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

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

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

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

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

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

     

    λλ

    11

    00

    q0q_0

    λ,R,q1λ, R, q_{1}

     

     

    q1q_1

    λ,S,q1λ, S, q_{1}

    0,R,q10, R, q_{1}

    1,S,q11, S, q_{1}

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

  • id 20171 балл

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

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

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

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

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

    a0a_{0}

    a1a_{1}

    ...

    q0q_{0}

    команда

    команда

    ...

    q1q_{1}

    команда

    команда

    ...

    ...

    ...

    ...

    ...

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

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

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

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

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

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

     

    λλ

    22

    11

    00

    q0q_0

    λ,R,q1λ, R, q_{1}

     

     

     

    q1q_1

    λ,S,q1λ, S, q_{1}

    0,R,q10, R, q_{1}

    2,R,q12, R, q_{1}

    1,R,q11, R, q_{1}

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

  • id 137261 балл

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

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

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

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

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

    a0a_{0}

    a1a_{1}

    ...

    q0q_{0}

    команда

    команда

    ...

    q1q_{1}

    команда

    команда

    ...

    ...

    ...

    ...

    ...

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

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

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

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

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

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

     

    λλ

    22

    11

    00

    q0q_0

    λ,R,q1λ, R, q_1

     

     

     

    q1q_1

    λ,S,q1λ, S, q_{1}

    0,R,q10, R, q_{1}

    2,R,q12, R, q_{1}

    1,R,q11, R, q_{1}

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

  • Архив ЕГЭid 136811 балл

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

    Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 102 идущих подряд цифр 9? В ответе запишите полученную строку.

    НАЧАЛО

    ПОКА нашлось (33333) ИЛИ нашлось (999)

    ЕСЛИ нашлось (33333)

    ТО заменить (33333, 99)

    ИНАЧЕ заменить (999, 3)

    КОНЕЦ ЕСЛИ

    КОНЕЦ ПОКА

    КОНЕЦ

  • Архив ЕГЭid 137061 балл

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

    Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 101 идущих подряд цифры 5? В ответе запишите полученную строку.

    НАЧАЛО

    ПОКА нашлось (33333) ИЛИ нашлось (555)

    ЕСЛИ нашлось (33333)

    ТО заменить (33333, 55)

    ИНАЧЕ заменить (555, 33)

    КОНЕЦ ЕСЛИ

    КОНЕЦ ПОКА

    КОНЕЦ

  • Архив ЕГЭid 141321 балл

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

    Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 99 идущих подряд цифр 9? В ответе запишите полученную строку.

    НАЧАЛО

    ПОКА нашлось (33333) ИЛИ нашлось (999)

    ЕСЛИ нашлось (33333)

    ТО заменить (33333, 99)

    ИНАЧЕ заменить (999, 399)

    КОНЕЦ ЕСЛИ

    КОНЕЦ ПОКА

    КОНЕЦ

  • Архив ЕГЭid 137731 балл

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

    Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 70 идущих подряд цифр 1? В ответе запишите полученную строку.

    НАЧАЛО

    ПОКА нашлось (1111) ИЛИ нашлось (2222)

    ЕСЛИ нашлось (1111)

    ТО заменить (1111, 22)

    ИНАЧЕ заменить (2222, 11)

    КОНЕЦ ЕСЛИ

    КОНЕЦ ПОКА

    КОНЕЦ

  • Архив ЕГЭid 136571 балл

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

    Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 108 идущих подряд цифр 7? В ответе запишите полученную строку.

    НАЧАЛО

    ПОКА нашлось (33333) ИЛИ нашлось (777)

    ЕСЛИ нашлось (33333)

    ТО заменить (33333, 7)

    ИНАЧЕ заменить (777, 3)

    КОНЕЦ ЕСЛИ

    КОНЕЦ ПОКА

    КОНЕЦ

  • Архив ЕГЭid 137451 балл

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

    Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 81 идущих подряд цифр 1? В ответе запишите полученную строку.

    НАЧАЛО

    ПОКА нашлось (11111) ИЛИ нашлось (888)

    ЕСЛИ нашлось (11111)

    ТО заменить (11111, 888)

    ИНАЧЕ заменить (888, 88)

    КОНЕЦ ЕСЛИ

    КОНЕЦ ПОКА

    КОНЕЦ

  • Архив ЕГЭid 137391 балл

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

    Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 70 идущих подряд цифр 1? В ответе запишите полученную строку.

    НАЧАЛО

    ПОКА нашлось (1111) ИЛИ нашлось (2222)

    ЕСЛИ нашлось (1111)

    ТО заменить (1111, 22)

    ИНАЧЕ заменить (2222, 11)

    КОНЕЦ ЕСЛИ

    КОНЕЦ ПОКА

    КОНЕЦ

  • id 369541 балл

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

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

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

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

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

    a0a_{0}

    a1a_{1}

    ...

    q0q_{0}

    команда

    команда

    ...

    q1q_{1}

    команда

    команда

    ...

    ...

    ...

    ...

    ...

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

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

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

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

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

    Алгоритм для Исполнителя:

    λλ

    11

    00

    q0q_{0}

    λ,L,q1λ, L, q_{1}

    q1q_{1}

    λ,S,q1λ, S, q_{1}

    0,L,q10, L, q_{1}

    1,L,q11, L, q_{1}

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

  • id 386361 балл

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

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

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

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

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

    a0a_{0}

    a1a_{1}

    ...

    q0q_{0}

    команда

    команда

    ...

    q1q_{1}

    команда

    команда

    ...

    ...

    ...

    ...

    ...

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

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

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

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

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

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

    λλ

    00

    11

    q0q_{0}

    λ,R,q1λ, R, q_{1}

    q1q_{1}

    λ,L,q2λ, L, q_{2}

    0,R,q10, R, q_{1}

    1,R,q11, R, q_1

    q2q_{2}

    λ,L,q3λ, L, q_3

    λ,L,q3λ, L, q_3

    q3q_3

    λ,S,q3λ, S, q_3

    1,S,q31, S, q_3

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

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

  • id 398111 балл

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

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

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

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

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

    a0a_{0}

    a1a_{1}

    ...

    q0q_{0}

    команда

    команда

    ...

    q1q_{1}

    команда

    команда

    ...

    ...

    ...

    ...

    ...

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

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

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

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

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

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

    λλ

    00

    11

    q0q_{0}

    λ,L,q1λ, L, q_{1}

    q1q_{1}

    1,R,q21, R, q_{2}

    1,R,q21, R, q_{2}

    0,L,q10, L, q_{1}

    q2q_{2}

    1,S,q21, S, q_{2}

    0,R,q20, R, q_{2}

    1,R,q21, R, q_{2}

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

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

  • id 403781 балл

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

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

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

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

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

    a0a_{0}

    a1a_{1}

    ...

    q0q_{0}

    команда

    команда

    ...

    q1q_{1}

    команда

    команда

    ...

    ...

    ...

    ...

    ...

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

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

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

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

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

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

    λλ

    00

    11

    q0q_{0}

    λ,L,q1λ, L, q_{1}

    q1q_{1}

    1,L,q11, L, q_{1}

    0,R,q20, R, q_{2}

    q2q_{2}

    1,S,q21, S, q_{2}

    0,R,q20, R, q_{2}

    1,R,q21, R, q_{2}

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

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

  • id 403821 балл

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

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

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

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

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

    a0a_{0}

    a1a_{1}

    ...

    q0q_{0}

    команда

    команда

    ...

    q1q_{1}

    команда

    команда

    ...

    ...

    ...

    ...

    ...

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

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

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

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

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

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

    λλ

    00

    11

    q0q_{0}

    λ,L,q1λ, L, q_{1}

    q1q_{1}

    λ,L,q2λ, L, q_2

    0,L,q10, L, q_{1}

    1,L,q11, L, q_1

    q2q_{2}

    1,R,q31, R, q_3

    q3q_{3}

    0,S,q30, S, q_3

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

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

  • id 403871 балл

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

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

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

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

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

    a0a_{0}

    a1a_{1}

    ...

    q0q_{0}

    команда

    команда

    ...

    q1q_{1}

    команда

    команда

    ...

    ...

    ...

    ...

    ...

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

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

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

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

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

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

    λλ

    00

    11

    q0q_{0}

    λ,L,q1λ, L, q_{1}

    q1q_{1}

    λ,R,q2λ, R, q_2

    0,L,q10, L, q_1

    1,L,q11, L, q_1

    q2q_{2}

    0,L,q30, L, q_3

    q3q_3

    1,S,q31, S, q_3

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

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

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

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

ИЮНЬ 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БВыше порога

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

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

Твой путь к высоким баллам начинается здесь от 100балльного репетитора
  • Все задания создают реальные эксперты ЕГЭ
  • Фильтры по предметам, номерам и темам
  • Никакой лишней рекламы: только задания и ответы
  • Можно готовиться в удобной мобильной версии

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

В школе дают теорию, в Банке — вся нужная практика для экзамена

Получай подсказки, если задача слишком сложная

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

Тренируйся по 10–15 минут каждый день

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

Отрабатывай западающие задания и темы

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

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

Тогда начинай тренироваться сегодня —
практика приведёт к высоким баллам

Хочешь поступить на бюджет? от 100балльного репетитора