Условие:
Построить машину Тьюринга, вычисляющую числовую функцию
f ( x1.x2...,xп).
Проверить работу построенной машины над некоторыми наборами
значений переменных.
\nf ( x , y , z , w ) = y + z + 1
Решение:
Ниже приведём представление задачи и описание машины с пояснениями шаг за шагом. В дальнейшем будем считать, что входной алфавит машины состоит из символов: 1 (единица, кодирующая одну единицу числа), 0 (разделитель) и B – символ пустой клетки (blank). Таким образом, входная последовательность имеет вид:
1^x 0 1^y 0 1^z 0 1^w
где 1^n означает последовательность из n единиц.
Общая идея решения состоит в следующем:
- Машина перемещается по ленте, пропуская числа x и w, так как они не используются.
- Сохраняются (копируются) в отдельную об...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Что нужно знать по теме:
Что нужно знать по теме
Алгоритм решения
Топ 3 ошибок
Что спросит препод
Похожие задачи