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 аналогично вправо и ...