Тренажеры

Курсы

Куратор

ЕГЭ Информатика 12. Выполнение алгоритмов для исполнителей Машина Тьюринга

12. Выполнение алгоритмов для исполнителей: машина тьюринга

1. Задание #298281

Задание было решено верно

Задание было решено неверно

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

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

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

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

	$a_0$	$a_1$	…	$a_{n-1}$
$q_0$	команда	команда	…	команда
$q_1$	команда	команда	…	команда
…	…	…	…	…
$q_{n-1}$	команда	команда	…	команда

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

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

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

Приведём пример выполнения программы, заданной таблично. На ленте записано неизвестное ненулевое количество расположенных подряд в соседних ячейках символов «Z», все остальные ячейки ленты заполнены пустым символом «$\lambda$». В начальный момент времени головка находится на неизвестном ненулевом расстоянии справа от самого правого символа «Z».

Программа

	$\lambda$	Z
$q_0$	$\lambda$, L, $q_0$	X, L, $q_1$
$q_1$	$\lambda$, S, $q_1$	X, L, $q_1$

заменяет на ленте все символы «Z» на «X» и останавливает исполнителя в первой ячейке слева от последовательности символов «X».

Возможное начальное состояние исполнителя:

…	$\lambda$	$\lambda$	Z	Z	Z	Z	$\lambda$	$\lambda$	…

Головка в состоянии $q_0$ стоит на восьмой ячейке.

Конечное состояние исполнителя после завершения выполнения программы:

…	$\lambda$	$\lambda$	X	X	X	X	$\lambda$	$\lambda$	…

Головка в состоянии $q_1$ стоит на второй ячейке.

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

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

	$\lambda$	$1$	$0$
$q_0$	$\lambda$, L, $q_1$
$q_1$	$\lambda$, S, $q_1$	$0$, S, $q_1$	$1$, L, $q_1$

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

Разберём, что делает программа. Головка стоит справа от последовательности на пустом символе, состояние $q_0$. Единственная заполненная клетка для $q_0$ — столбец «$\lambda$»: головка ничего не меняет, сдвигается влево и переходит в $q_1$. Теперь она стоит на самом правом символе последовательности.

Дальше вся работа идёт в состоянии $q_1$, и вариантов три. Если под головкой ноль, он заменяется на единицу, и головка сдвигается влево. Если под головкой единица, она заменяется на ноль и исполнитель останавливается. Если под головкой пустой символ, исполнитель тоже останавливается.

Значит программа идёт от правого края влево, переворачивая нули в единицы, пока не встретит первую единицу — превращает её в ноль и останавливается. Обозначим через $k$ количество нулей в хвосте справа, то есть до этой первой единицы.

Посчитаем баланс нулей. Из хвоста ушло $k$ нулей, зато встреченная единица стала нулём — прибавился один. Если исходно нулей было $Z$, то после работы их стало $Z — k + 1$. По условию это $343$, откуда $Z = 342 + k$.

Чтобы получить максимум нулей, надо взять как можно большее $k$. Но в последовательности должна быть хотя бы одна единица — иначе исполнитель дойдёт до пустого символа, все нули превратятся в единицы, и на ленте останется ноль нулей, что условию не удовлетворяет. Значит нулей не больше $999$, то есть $Z = 342 + k \le 999$, откуда $k \le 657$.

Возьмём $k = 657$. Тогда $Z = 342 + 657 = 999$: единственная единица стоит на $343$-й позиции, слева от неё $342$ нуля, справа $657$ нулей. После работы программы правые $657$ нулей станут единицами, а единица на $343$-й позиции станет нулём. Нулей останется $342 + 1 = 343$, что и требуется.

Проверим моделированием на языке Python.

def run(seq):
    tape = list(seq)
    pos = len(seq)                # ячейка справа от последовательности
    st = 'q0'
    while True:
        c = tape[pos] if 0 <= pos < len(tape) else 'L'   # 'L' — символ лямбда
        if st == 'q0':
            if c == 'L':
                pos -= 1
                st = 'q1'
            else:
                break
        else:
            if c == 'L':
                break                       # остановка
            if c == '1':
                tape[pos] = '0'
                break                       # остановка
            tape[pos] = '1'                 # был ноль
            pos -= 1
    return ''.join(tape)

seq = '0'*342 + '1' + '0'*657
print(seq.count('0'), run(seq).count('0'))   # 999 343

Программа подтверждает: в исходной последовательности $999$ нулей, после выполнения остаётся ровно $343$.

Показать

2. Задание #298287

Задание было решено верно

Задание было решено неверно

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

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

	$a_0$	$a_1$	…	$a_{n-1}$
$q_0$	команда	команда	…	команда
$q_1$	команда	команда	…	команда
…	…	…	…	…
$q_{n-1}$	команда	команда	…	команда

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

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

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

Приведём пример выполнения программы, заданной таблично. На ленте записано неизвестное ненулевое количество расположенных подряд в соседних ячейках символов «Z», все остальные ячейки ленты заполнены пустым символом «$\lambda$». В начальный момент времени головка находится на неизвестном расстоянии справа от самого правого символа «Z».

Программа

	$\lambda$	Z
$q_0$	$\lambda$, L, $q_0$	X, L, $q_1$
$q_1$	$\lambda$, L, $q_1$	X, L, $q_2$
$q_2$	$\lambda$, S, $q_2$	X, L, $q_2$

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

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda$, L, $q_1$
$q_1$	$1$, L, $q_2$	$0$, L, $q_1$	$1$, L, $q_1$
$q_2$	$\lambda$, S, $q_2$

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

Разберём, что делает программа. Головка стоит справа от числа на пустом символе, состояние $q_0$. Единственная заполненная клетка для $q_0$ — столбец «$\lambda$»: символ не меняется, головка сдвигается влево и переходит в $q_1$. Теперь она стоит на младшем разряде числа.

В состоянии $q_1$ обе цифровые команды устроены одинаково: символ записывается тот же самый, головка сдвигается влево, состояние остаётся $q_1$. То есть машина просто пробегает всё число справа налево, ничего не меняя.

Когда головка выходит за левый край числа и видит пустой символ, срабатывает команда $1$, L, $q_2$: в эту ячейку записывается единица, головка сдвигается влево и переходит в $q_2$. Там она видит пустой символ и останавливается.

Итог: программа приписывает единицу слева от двоичной записи числа. Никакие цифры самого числа не меняются.

Переведём $2027$ в двоичную систему. $2027 = 1024 + 512 + 256 + 128 + 64 + 32 + 8 + 2 + 1$, то есть $2027_{10} = 11111101011_2$. В записи $11$ разрядов.

Приписываем слева единицу: получается $111111101011_2$. Новая единица встала в разряд $2^{11} = 2048$, все остальные разряды сохранились, поэтому результат равен $2048 + 2027 = 4075$.

s = bin(2027)[2:]        # 11111101011
r = '1' + s              # приписываем единицу слева
print(r, int(r, 2))      # 111111101011 4075

Показать

3. Задание #298427

Задание было решено верно

Задание было решено неверно

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

	$a_0$	$a_1$	…	$a_{n-1}$
$q_0$	команда	команда	…	команда
$q_1$	команда	команда	…	команда
…	…	…	…	…
$q_{n-1}$	команда	команда	…	команда

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

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

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

Приведём пример выполнения программы, заданной таблично. На ленте записано неизвестное ненулевое количество расположенных подряд в соседних ячейках символов «$Z$», все остальные ячейки ленты заполнены пустым символом «$\lambda$». В начальный момент времени головка находится на неизвестном расстоянии справа от самого правого символа «$Z$».

Программа

	$\lambda$	$Z$
$q_0$	$\lambda$, $L$, $q_0$	$X$, $L$, $q_1$
$q_1$	$\lambda$, $L$, $q_1$	$X$, $L$, $q_2$
$q_2$	$\lambda$, $S$, $q_2$	$X$, $L$, $q_2$

заменяет на ленте все символы «$Z$» на «$X$» и останавливает исполнителя в первой ячейке слева от последовательности символов «$X$».

Возможное начальное состояние исполнителя:

…	$\lambda$	$\lambda$	$Z$	$Z$	$Z$	$Z$	$\lambda$	$\lambda$	…
								$q_0$

Конечное состояние исполнителя после завершения выполнения программы:

…	$\lambda$	$\lambda$	$X$	$X$	$X$	$X$	$\lambda$	$\lambda$	…
		$q_2$

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

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda$, $L$, $q_1$
$q_1$	$1$, $L$, $q_2$	$1$, $S$, $q_2$	$0$, $L$, $q_1$
$q_2$	$\lambda$, $S$, $q_2$

Сначала разберёмся, что делает программа, безотносительно конкретного числа.

Состояние $q_0$ отработает ровно один такт: головка стоит на пустой ячейке справа от числа, ничего не меняет, сдвигается влево и переходит в $q_1$. Теперь она на младшем (самом правом) разряде числа.

Состояние $q_1$ — рабочее, и его три команды складываются в знакомый алгоритм: если под головкой $1$, она записывает $0$ и идёт влево, оставаясь в $q_1$; если под головкой $0$, она записывает $1$ и останавливается; если под головкой $\lambda$ (число кончилось, а мы всё ещё идём влево), она записывает $1$, сдвигается влево и переходит в $q_2$.

Состояние $q_2$ — терминальное: команда $\lambda$, $S$, $q_2$ немедленно завершает работу.

Это в точности прибавление единицы к двоичному числу «столбиком», справа налево: единицы младших разрядов превращаются в нули (перенос идёт дальше), первый встреченный ноль становится единицей и перенос гасится. Если же нулей в числе нет вовсе, перенос выходит за пределы записи, и слева дописывается новая единица.

Теперь конкретное число. Переведём $1023$ в двоичную систему: $1023 = 2^{10} — 1 = \underbrace{11\ldots1}_{10}$, то есть на ленте записано $1111111111$.

Нулей в этой записи нет, поэтому головка проходит все $10$ единиц, превращая каждую в $0$, и упирается в пустую ячейку слева. Там срабатывает команда $1$, $L$, $q_2$: записывается старшая единица, головка уходит влево и останавливается в состоянии $q_2$.

На ленте получается $10000000000$ — единица и десять нулей. Это $2^{10} = 1024$.

Тот же результат даёт и общий смысл программы: она прибавляет к числу единицу, а $1023 + 1 = 1024$.

Показать

4. Задание #298428

Задание было решено верно

Задание было решено неверно

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

	$a_0$	$a_1$	…	$a_{n-1}$
$q_0$	команда	команда	…	команда
$q_1$	команда	команда	…	команда
…	…	…	…	…
$q_{n-1}$	команда	команда	…	команда

Программа

	$\lambda$	$Z$
$q_0$	$\lambda$, $L$, $q_0$	$X$, $L$, $q_1$
$q_1$	$\lambda$, $L$, $q_1$	$X$, $L$, $q_2$
$q_2$	$\lambda$, $S$, $q_2$	$X$, $L$, $q_2$

Возможное начальное состояние исполнителя:

…	$\lambda$	$\lambda$	$Z$	$Z$	$Z$	$Z$	$\lambda$	$\lambda$	…
								$q_0$

Конечное состояние исполнителя после завершения выполнения программы:

…	$\lambda$	$\lambda$	$X$	$X$	$X$	$X$	$\lambda$	$\lambda$	…
		$q_2$

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

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda$, $L$, $q_1$
$q_1$	$\lambda$, $R$, $q_2$	$0$, $L$, $q_1$	$1$, $L$, $q_1$
$q_2$			$0$, $L$, $q_3$
$q_3$	$1$, $S$, $q_3$

Разберём, что делает программа, не глядя пока на конкретное число.

Состояние $q_0$ работает один такт: головка стоит на пустой ячейке справа от числа, ничего не пишет, сдвигается влево и переходит в $q_1$. Теперь она на младшем разряде.

Состояние $q_1$ — «пробег влево». Обе команды для цифр записывают в ячейку тот же самый символ ($0 \to 0$, $1 \to 1$) и двигают головку влево, то есть число не меняется, головка просто проезжает всю запись до конца. Дойдя до пустой ячейки слева от числа, головка по команде $\lambda$, $R$, $q_2$ возвращается на один шаг вправо — то есть встаёт ровно на старший разряд — и переходит в $q_2$.

Состояние $q_2$ определено только для символа $1$ — и это законно: запись без ведущих нулей всегда начинается с единицы, так что пара «$q_2$ и $0$» невозможна. Команда $0$, $L$, $q_3$ стирает старшую единицу (пишет на её место $0$) и уводит головку влево, на пустую ячейку.

Состояние $q_3$ по команде $1$, $S$, $q_3$ записывает туда единицу и останавливается.

Что получилось в итоге: старшая единица как бы переехала на одну ячейку влево, а на её прежнем месте появился ноль. Если исходное число содержало $n$ разрядов и равнялось $2^{n-1} + r$, где $r$ — значение младших $n-1$ разрядов, то новая запись имеет вид $1,0,\ldots$ и равна $2^{n} + r$. Иначе говоря, программа прибавляет к числу его старший разряд: результат равен $V + 2^{n-1}$.

Теперь конкретное число. Переведём $2025$ в двоичную систему: $$2025 = 1024 + 512 + 256 + 128 + 64 + 32 + 8 + 1 = 11111101001_2.$$

В записи $11$ разрядов, старший разряд равен $2^{10} = 1024$, остаток $r = 2025 — 1024 = 1001$.

Головка проезжает все $11$ цифр влево, возвращается на старшую единицу, заменяет её нулём и дописывает единицу слева. На ленте оказывается $101111101001$, то есть $$2^{11} + 1001 = 2048 + 1001 = 3049.$$

Тот же ответ даёт и формула: $2025 + 1024 = 3049$.

Показать

5. Задание #298432

Задание было решено верно

Задание было решено неверно

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

	$a_0$	$a_1$	…	$a_{n-1}$
$q_0$	команда	команда	…	команда
$q_1$	команда	команда	…	команда
…	…	…	…	…
$q_{n-1}$	команда	команда	…	команда

Программа

	$\lambda$	$Z$
$q_0$	$\lambda$, $L$, $q_0$	$X$, $L$, $q_1$
$q_1$	$\lambda$, $L$, $q_1$	$X$, $L$, $q_2$
$q_2$	$\lambda$, $S$, $q_2$	$X$, $L$, $q_2$

Возможное начальное состояние исполнителя:

…	$\lambda$	$\lambda$	$Z$	$Z$	$Z$	$Z$	$\lambda$	$\lambda$	…
								$q_0$

Конечное состояние исполнителя после завершения выполнения программы:

…	$\lambda$	$\lambda$	$X$	$X$	$X$	$X$	$\lambda$	$\lambda$	…
		$q_2$

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda$, $L$, $q_1$
$q_1$	$\lambda$, $R$, $q_2$	$0$, $L$, $q_1$	$1$, $L$, $q_1$
$q_2$			$0$, $L$, $q_3$
$q_3$	$1$, $S$, $q_3$

Разберём, что делает программа, не глядя пока на конкретное число.

Состояние $q_3$ по команде $1$, $S$, $q_3$ записывает туда единицу и останавливается.

Теперь конкретное число. Переведём $2027$ в двоичную систему: $$2027 = 1024 + 512 + 256 + 128 + 64 + 32 + 8 + 2 + 1 = 11111101011_2.$$

В записи $11$ разрядов, старший разряд равен $2^{10} = 1024$, остаток $r = 2027 — 1024 = 1003$.

Головка проезжает все $11$ цифр влево, возвращается на старшую единицу, заменяет её нулём и дописывает единицу слева. На ленте оказывается $101111101011$, то есть $$2^{11} + 1003 = 2048 + 1003 = 3051.$$

Тот же ответ даёт и формула: $2027 + 1024 = 3051$.

Показать

03:50:00

Решено заданий: 0 из

0 заданий сегодня

12. Выполнение алгоритмов для исполнителей: машина тьюринга

Сообщить об ошибке в задании

Сообщить об ошибке в задании

Сообщить об ошибке в задании

Сообщить об ошибке в задании

Сообщить об ошибке в задании