AC8712 — Редактор и машина Тьюринга: ответ и решение

Впишите правильный ответ.

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

Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном
из множества допустимых состояний Q = {q₀, q₁, …, q_n_$-$₁}. В начальный момент времени головка находится в начальном состоянии q₀.

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

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

	a₀	a₁	…	a_n_{$-$ 1}
q₀	команда	команда	…	команда
q₁	команда	команда	…	команда
…	…	…	…	…
q_n_$-$₁	команда	команда	…	команда

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

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

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

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

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

Программа

	λ	Z
q₀	λ, L, q₀	X, L, q₁
q₁	λ, L, q₁	X, L, q₂
q₂	λ, S, q₂	X, L, q₂

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

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

…	λ	λ	Z	Z	Z	Z	λ	λ	…
								q₀

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

…	λ	λ	X	X	X	X	λ	λ	…
		q₂

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

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

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

	λ	0	1
q₀	λ, L, q₁
q₁	λ, R, q₂	0, L, q₁	1, L, q₁
q₂			λ, R, q₃
q₃		1, S, q₃	1, S, q₃

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

Решение задания EGEINFAC8712

Ответ: 1002

Решение.
Переведём исходное число в двоичную систему: 1514 = 1024 + 256 + 128 + 64 + 32 + 8 + 2 = 10111101010₂.
Головка начинает в состоянии q₀ в пустой ячейке сразу справа от числа. По первой команде она сохраняет пустой символ, делает шаг влево и переходит в q₁.
Далее читаем именно столбец текущего символа и строку текущего состояния. Сначала записывается символ, затем выполняется сдвиг; S означает остановку после записи.
В состоянии q₁: λ → λ,R,q₂; 0 → 0,L,q₁; 1 → 1,L,q₁.
В состоянии q₂: 1 → λ,R,q₃.
В состоянии q₃: 0 → 1,S,q₃; 1 → 1,S,q₃.
Проследим работу. Позиции исходного слова считаем от 0 слева; позиция −1 — первая пустая ячейка слева:
Шаг 1: позиция 11, q₀, читаем λ, записываем λ; шаг влево, состояние q₁.
Шаг 2: позиция 10, q₁, читаем 0, записываем 0; шаг влево, состояние q₁.
Шаг 3: позиция 9, q₁, читаем 1, записываем 1; шаг влево, состояние q₁.
Шаг 4: позиция 8, q₁, читаем 0, записываем 0; шаг влево, состояние q₁.
Шаг 5: позиция 7, q₁, читаем 1, записываем 1; шаг влево, состояние q₁.
Шаг 6: позиция 6, q₁, читаем 0, записываем 0; шаг влево, состояние q₁.
Шаг 7: позиция 5, q₁, читаем 1, записываем 1; шаг влево, состояние q₁.
Шаг 8: позиция 4, q₁, читаем 1, записываем 1; шаг влево, состояние q₁.
Шаг 9: позиция 3, q₁, читаем 1, записываем 1; шаг влево, состояние q₁.
Шаг 10: позиция 2, q₁, читаем 1, записываем 1; шаг влево, состояние q₁.
Шаг 11: позиция 1, q₁, читаем 0, записываем 0; шаг влево, состояние q₁.
Шаг 12: позиция 0, q₁, читаем 1, записываем 1; шаг влево, состояние q₁.
Шаг 13: позиция -1, q₁, читаем λ, записываем λ; шаг вправо, состояние q₂.
Шаг 14: позиция 0, q₂, читаем 1, записываем λ; шаг вправо, состояние q₃.
Шаг 15: позиция 1, q₃, читаем 0, записываем 1; останавливаемся.
На ленте осталось слово 1111101010. Пустые клетки в запись числа не включаются.
1111101010₂ = 512 + 256 + 128 + 64 + 32 + 8 + 2 = 1002.
Проверка: последняя команда содержит S; выполнено 15 шагов, запись остаётся непрерывной двоичной последовательностью.
Ответ: 1002.

КЭС:	3.3 Определение возможных результатов работы простейших алгоритмов управления исполнителями и вычислительных алгоритмов. Определение исходных данных, при которых алгоритм может дать требуемый результат
Тип ответа:	Краткий ответ

Задание EGEINFAC8712: Редактор и машина Тьюринга

Решение задания EGEINFAC8712

Помочь улучшить сайт

Комментарии к решению