Условие:
1. Построить машину Тьюринга, вычисляющую числовую функцию f(x1, x2, …, xn);
2. Проверить работу построенной машины над некоторыми наборами значений переменных.
Решение:
Принимаю следующие соглашения:
-
внешний алфавит МТ обязательно содержит символ a0 символ пустой ячейки;
внутренний алфавит (алфавит состояний) МТ обязательно содержит символы q0 и q1 конечное и начальное состояния. В состоянии q1 МТ начинает работу, в состоянии q0 заканчивает;
нначальная конфигурация МТ находясь в состоянии q1 МТ обозревает крайнюю левую непустую ячейку, т.е.НК=a0 q1 a0, где , слово в алфавите A\{a0}; конечная конфигурация МТ q0 'a0, где ', слово в алфавите A\{a0};
всякая команда МТ имеет вид ai qjam qn L|R|E, где L движение на одну ячейку влево, R аналогично вправо и ...