Под машиной Тьюринга понимается некоторая гипотетическая (абстрактная) машина, состоящая из следующих частей:
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 , или работает бесконечно, когда не определена.