Построить машину Тьюринга, вычисляющую числовую функцию f(x1, x2, …, xn);
2. Проверить работу построенной машины над некоторыми наборами значений переменных.
fx, y, z=0, если x=0,y, если x≠0.
Решение
Принимаю следующие соглашения:
внешний алфавит МТ обязательно содержит символ a0 — символ пустой ячейки;
внутренний алфавит (алфавит состояний) МТ обязательно содержит символы q0 и q1 — конечное и начальное состояния. В состоянии q1 МТ начинает работу, в состоянии q0 — заканчивает;
начальная конфигурация МТ — находясь в состоянии q1 МТ обозревает крайнюю левую непустую ячейку, т.е.НК=…a0q1αa0…, где α, — слово в алфавите A\{a0}; конечная конфигурация МТ — …q0α'a0…, где α', — слово в алфавите A\{a0};
всякая команда МТ имеет вид aiqj→amqnL|R|E, где L — движение на одну ячейку влево, R — аналогично вправо и E — без движения, am может совпадать с ai, а qn — c qj.
Унарный алфавит A = { a0, 0, 1}, причем 0 используется в служебных целях — для отделения x, y, z друг от друга. Значение аргументов запишется в этом случае как …a001x+101y+101z+10a0…, где количество 1 равно x+1, y+1, z+1 соответственно
. Нулю, таким образом соответствует 1. Итак,
НК = …a0q101x+101y+101z+10a0…
КК = …a0q0010a0… или …a0q001y+10a0…
Опишем алгоритм работы МТ:
Находясь в состоянии q1 и наблюдая в текущей ячейке 0 (начала работы) МТ не меняя состояния сдвигается вправо где находится 1.
Находясь в состоянии q1 и наблюдая в текущей ячейке 1 МТ изменяет состояния на q2 и сдвигается вправо.
Если находясь в состоянии q2 МТ наблюдает 0 то это означает, что x = 0 и fx, y, z=0 ; если же в состоянии q2 МТ наблюдает 1 то это означает, x 0 и fx, y, z=y;
при x = 0 стираем y и z, после чего возвращаемся к первому нулю,
при x 0 возвращаемся в начало, стираем х, пропускаем у, стираем z, после чего возвращаемся к первому нулю.
0q1→0q1R
начало работы
1q1→1q2R
0q2→0q3R x=0 принятие решения
1q2→1q4L x≠0
1q3→a0q3R стираем 1, двигаемся вправо удаление y и z при x=0удаление z при x≠0
0q3→a0q3R стираем 0, двигаемся вправо
a0q3→a0q7L аргументы удалены, переход к КК
1q4→1q4L пропускаем 1, двигаемся влево
0q4→a0q5R стираем первый 0, двигаемся вправо удаление x при x≠0
1q5→a0q5R стираем 1, двигаемся вправо
0q5→0q6R пропускаем 0, двигаемся вправо пропуск y при x≠0
1q6→1q6R пропускаем 1, двигаемся вправо
0q6→0q3R пропускаем 0, двигаемся вправо
a0q7→a0q7L пропускаем a0, двигаемся влево установка КК
0q7→0q8L пропускаем 0, двигаемся влево
1q8→1q8L пропускаем 1, двигаемся влево
0q8→0q8L пропускаем 0, двигаемся влево
a0q8→a0q0R конец работы МТ
Проверим работу построенной МТ при вычислении f0, 1, 1 и f1, 2, 0, т.е
Задать вопрос
на новый заказ в Автор24.
