Определение машины Тьюринга (МТ)

Под машиной Тьюринга понимается некоторая гипотетическая (абстрактная) машина, состоящая из следующих частей:

1) бесконечной в обе стороны ленты, разбитой на ячейки, в каждой из ячеек может быть записан только один символ из алфавита , а также пустой символ l;

2) рабочей головки или управляющего устройства (УУ), которое в каждый момент времени может находиться в одном из состояний множества . В каждом из состояний головка размещается напротив ячейки и может считывать (обозревать) или записывать в нее букву из алфавита А.

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

Функционирование МТ состоит из последовательности элементарных шагов (тактов). На каждом шаге выполняются следующие действия:

1) управляющее устройство считывает (обозревает) символ ;

2) в зависимости от своего состояния и обозреваемого символа

УУ вырабатывает символ и записывает его в обозреваемую ячейку (возможно );

3) головка перемещается на одну ячейку вправо (R), влево (L) или остается на месте (E);

4) головка переходит в другое внутреннее состояние (возможно ).

Состояние называется начальным, – заключительным. При переходе в заключительное состояние машина останавливается.

Полное состояние МТ называется конфигурацией. Это распределение букв по ячейкам ленты, состояние рабочей головки и обозреваемая ячейка. Конфигурация в такте t записывается в виде: , где – подслово слева от обозреваемой ячейки, – буква в обозреваемой ячейке, – подслово справа. Начальная конфигурация и конечная называются стандартными.

Для описания работы МТ существует 3 способа:

1) система команд вида

2) функциональная таблица;

3) граф (диаграмма) переходов.

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

Наиболее употребительной является унарная система, состоящая из одного символа – . Число Х в унарной системе счисления на ленте записывается словом , (сокращенно ) в алфавите А={ }.

Пример 1. Операция сложения двух чисел в унарном коде.

Начальная конфигурация: . Конечная конфигурация: , т.е. сложение фактически сводится к приписыванию числа b к числу a. Для этого первый символ стирается, а * заменяется на .

Система команд при и .

Комментарий к системе команд

1. – стирание первого символа .

Если в обозреваемой ячейке записан символ и МТ находится в состоянии _, тогда состояние изменяется на , обозреваемый символ заменяется на пустой, УУ сдвигается вправо.

2. – стирание символа , первый аргумент равняется 0.

Если в обозреваемой ячейке записан символ и МТ в состоянии (первый аргумент равняется 0)_, тогда состояние изменяется на , обозреваемый символ заменяется на пустой, УУ сдвигается вправо.

3. – сдвиг вправо.

Если в обозреваемой ячейке записан символ, записан символ и МТ находится в состоянии _, тогда состояние и обозреваемый символ не изменяются, УУ сдвигается вправо.

4. – стирание символа .

Если в обозреваемой ячейке записан символ и МТ находится в состоянии _, тогда состояние изменяется на , и обозреваемый символ заменяется на , УУ сдвигается влево (конец первого аргумента).

5. – сдвиг влево.

Если в обозреваемой ячейке записан символ и МТ находится в состоянии , тогда состояние и обозреваемый символ не изменяются, УУ сдвигается влево.

6. – конец алгоритма, останов.

Если в обозреваемой ячейке записан символ и МТ находится в состоянии _, тогда состояние изменяется на , обозреваемый символ не изменяется, УУ сдвигается вправо (конец алгоритма, УУ расположено в начале рабочей зоны).

Описание МТ в виде функциональной таблицы:

	|	*	l
			-
			-
		-

Описание МТ в виде диаграммы переходов

Вычисление на МТ словарной функции будем понимать следующим образом. Пусть в начальной конфигурации на ленте записано слово . Если значение определено, то конечного числа шагов (тактов) машина должна перейти в заключительную конфигурацию, в которой на ленте записано слово . В противном случае МТ должна работать бесконечно.

Числовая функция правильно вычислима (или просто вычислима) по Тьюрингу, если существует МТ, которая переводит конфигурацию в конфигурацию , когда = y, или работает бесконечно, когда не определена.