Символьные конструкции

Алфавитом будем называть любое конечное множество попарно различных знаков, называемых буквами (символами) этого алфавита. Алфавит будем обозначать заглавными буквами, например:

Символом l будем обозначать пустой символ.

Словом в данном алфавите называется любая конечная (в том числе и пустая) последовательность букв этого алфавита. Слова будем обозначать малыми греческими буквами.

Например: a = алгоритм – слово в алфавите А; b = 1010100 – слово в алфавите В; – слово в алфавите С.

Пустое слово будем обозначать L.

Длина слова a (обозначается |a|) – это количество букв в слове.

Определим некоторые отношения и операции над словами.

Равенство слов в алфавите А определяется индуктивно:

а) пустые слова равны

б) если слово a равно слову b, то a b =b b, где b –буква в алфавите А.

Если слово a является частью слова b, то говорят, что имеет место вхождение слова a в слово b (слово a называется подсловом слова b). Это можно записать следующим образом: , где – слова в алфавите А.

Слово a называется началом слова b, если ; концом слова b, если . Слово длины n, составленное из буквы а, повторенной n раз, будем обозначать , например xyxxxyyyy = .

Операция (и результат) приписывания слов a и b друг к другу называется конкатенацией (обозначается a||b). Например, если .

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

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

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, или работает бесконечно, когда не определена.