Машина Тьюринга

Оператор определяет наименьшее значение у, при котором при фиксированном значении. Принято обозначение

(4.7)

(Читается: «наименьшее такое, что »). Аналогично определяется функция многих переменных:

(4.8)

Для вычисления функции существует следующий алгоритм:

1. Вычисляется . Если это значение функции равно нулю, то . Если , то осуществляется переход к следующему шагу.

2. Вычисляется . Если это значение функции равно нулю, то . Если , то осуществляется переход к следующему шагу. И т. д.

Если окажется, что для всех функция , то функция считается неопределенной.

ПРИМЕР

Дана функция . Необходимо определить при

Таким образом,

Функция называется частично рекурсивной, если она получена из простейших функций за конечное число шагов на основе правил подстановки, примитивной рекурсии или m - оператора.

Функция называется примитивно рекурсивной, если она может быть получена из простейших функций за конечное число шагов на основе правил подстановки, примитивной рекурсии.

Функция называется общерекурсивно й, если она частично рекурсивная и всюдуопределенная.

4. Бесконечная лента Бесконечная лента характеризует память машины. Она разбита на клеточки. В каждую клеточку может быть записан только один символ из внешнего алфавита.

5. Управляющая головка. Управляющая головка (УГ) передвигается вдоль ленты и может останавливаться напротив какой-либо клетки, т. е. считывать символ

6. Управляющая головка. Управляющая головка (УГ) передвигается вдоль ленты и может останавливаться напротив какой-либо клетки, т. е. считывать символ.

Рис. 4.1. Функциональная схема машины Тьюринга.

Таким образом, машина Тьюринга может быть представлена в виде четверки:

(4.9)

Работа машины Тьюринга:

Информация, хранящаяся на ленте, является набором символов из внешнего алфавита. Начальное состояние управляющей головки характеризуется символом внутреннего алфавита . Работа машины складывается из тактов. В течение любого такта машина Тьюринга осуществляет следующие действия: машина Тьюринга находится во внутреннем состоянии , считывает входной символ и по таблице работы совершает операцию сдвига , переходя в состояние , при этом входное слово заменяется на :

Если в результате операции машина перейдет в состояние , то работа машины останавливается. Если состояние недостижимо, то значит по данному входному слову машина Тьюринга не достигает конечного состояния и алгоритма для данного входного слова не существует.

ПРИМЕР

Построить машину Тьюринга, которая будет стирать последнюю единицу в последовательности единиц.

Внешний алфавит - . Внутренний алфавит -, при этом состояние .сохраняется до тех пор, пока не будет найден конец последовательности единиц, состояние - стирание последней единицы. При этом следует заметить, что ситуация в работе машины Тьюринга невозможна, поэтому соответствующая клеточка доопределена произвольно, например . Начальное состояние на начале последовательности единиц. Рабочая программа машины Тьюринга имеет вид:

Проверим работоспособность машины Тьюринга:

1.

2.

3.

4.

5.