Теория:
Характеристика задания
1. Тип ответа: запись числового значения.
2. Структура содержания задания: дана программа для машины Тьюринга.
3. Уровень сложности задания: повышенный.
4. Примерное время выполнения: \(6\) минут.
5. Количество баллов: \(1\).
6. Требуется специальное программное обеспечение: необязательно.
7. Задание проверяет умение выполнять алгоритм для конкретного исполнителя с фиксированным набором команд.
Пример задания
Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов \(A = {a0, a1, ..., a(n~–1)})\), включая специальный пустой символ \(a0\). Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний \(Q = {q0, q1, ..., q(n~–1)}\). В начальный момент времени головка находится в начальном состоянии \(q0\). На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может переместиться в ячейку справа или слева от текущей, не меняя находящийся в ней символ, или заменить символ в текущей ячейке без сдвига в соседнюю ячейку. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии. Программа работы исполнителя МТ задаётся в табличном виде.
\(a0\) | \(a1\) | ... | \(a(n-1)\) | |
\(q0\) | команда | команда | ... | команда |
\(q1\) | команда | команда | ... | команда |
... | ... | ... | ... | ... |
\(q(n-1)\) | команда | команда | ... | команда |
В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце — возможные состояния головки. На пересечении \(i\)-й строки и \(j\)-го столбца находится команда, которую выполняет МТ, когда головка обозревает \(j\)-й символ, находясь в \(i\)-м состоянии. Если пара «символ — состояние» невозможна, то клетка для команды остаётся пустой. Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент — записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент — один из четырёх символов \(L\), \(R\), \(N\), \(S\). Символы \(L\) и \(R\) означают сдвиг в левую или правую ячейки соответственно, \(N\) — отсутствие сдвига, \(S\) — завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент — новое состояние головки после выполнения команды. Например, команда \(0\), \(L\), \(q3\) выполняется следующим образом: в текущую ячейку записывается символ \(0\), затем головка сдвигается в соседнюю слева ячейку и переходит в состояние \(q3\).
Приведём пример выполнения программы, заданной таблично.
На ленте записано неизвестное ненулевое количество расположенных подряд в соседних ячейках символов \(Z\), все остальные ячейки ленты заполнены пустым символом \(λ\). В начальный момент времени головка находится на неизвестном ненулевом расстоянии справа от самого правого символа \(Z\).
На ленте записано неизвестное ненулевое количество расположенных подряд в соседних ячейках символов \(Z\), все остальные ячейки ленты заполнены пустым символом \(λ\). В начальный момент времени головка находится на неизвестном ненулевом расстоянии справа от самого правого символа \(Z\).
Программа
\(λ\) | \(Z\) | |
\(q0\) | \(λ\), \(L\), \(q0\) | \(X\), \(L\), \(q1\) |
\(q1\) | \(λ\), \(S\), \(q1\) | \(X\), \(L\), \(q1\) |
заменяет на ленте все символы \(Z\) на \(X\) и останавливает исполнителя в первой ячейке слева от последовательности символов \(X\).
Возможное начальное состояние исполнителя:
... | \(λ\) | \(λ\) | \(Z\) | \(Z\) | \(Z\) | \(Z\) | \(λ\) | \(λ\) | … |
Конечное состояние исполнителя после завершения выполнения программы:
... | \(λ\) | \(λ\) | \(X\) | \(X\) | \(X\) | \(X\) | \(λ\) | \(λ\) | … |
Выполни задание.
На ленте в соседних ячейках записана последовательность из \(1000\) символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами \(λ\). В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности. Программа работы исполнителя:
\(λ\) | \(1\) | \(0\) | |
\(q0\) | \(λ\), \(L\), \(q1\) | ||
\(q1\) | \(λ\), \(S\), \(q1\) | \(0\), \(S\), \(q1\) | \(1\), \(L\), \(q1\) |
После выполнения программы на ленте осталось ровно \(343\) нуля. Определи максимально возможное число нулей в исходной последовательности.
Разберём работу программы исполнителя МТ с учётом заданных условий.
Исполнитель стартует в ячейке, расположенной непосредственно справа от анализируемой последовательности. Первым действием он выполняет команду перемещения влево — в сторону начала последовательности.
Логика работы алгоритма следующая.
При обнаружении символа \(1\) или \(λ\) выполнение программы немедленно завершается.
Если исполнитель встречает символ \(0\), он выполняет два действия:
заменяет \(0\) на \(1\);
перемещается на одну ячейку влево.
Предположим, что исходная последовательность содержит \(1000\) символов и полностью состоит из нулей. В таком случае исполнитель последовательно заменит каждый \(0\) на \(1\), двигаясь от правого края к левому.
По условию после завершения работы программы в последовательности осталось \(343\) символа \(0\). Это позволяет сделать вывод о структуре исходной ленты:
слева располагались \(343\) нуля, которые исполнитель не успел обработать;
далее следовал хотя бы один символ \(1\) (или \(λ\)), ставший причиной остановки программы.
Чтобы определить максимально возможное количество нулей в исходной последовательности, нужно вычислить максимальное число \(0\) справа от стоп‑символа (\(1\)/\(λ\)).
Расчёт:
общая длина последовательности: \(1000\) символов;
количество \(0\) слева от стоп‑символа: \(343\);
стоп‑символ (\(1\)): \(1\) символ;
максимально возможное количество \(0\) справа от стоп‑символа: \(1000−343−1=656\).
Таким образом, наибольшее возможное число нулей в исходной последовательности складывается из двух частей:
\(343\) нуля слева от стоп‑символа (неизменённые);
\(656\) нулей справа от стоп‑символа (которые исполнитель успел заменить на \(1\)).
Итоговый результат: \(343+656=999\) символов \(0\).
Ответ: \(999\).