Машина Тьюринга. Теоретические сведения

Теоретические сведения

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

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

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

Информационная лента бесконечной длины представляет собой последовательность ячеек, в каждую из которых может быть записан в точности только один символ из множества символов алфавита А = { a₀; a₁; a₂;... a_n}; последовательность символов на ленте формирует слово a = (a₁; a₂;... a_i). Информационную ленту чаще всего называют внешней памятью машины Тьюринга; поскольку символы на информационной ленте предназначены для считывания, то множество этих символов тождественно множеству терминальных символов формальной грамматики. Один из символов алфавита А выделяют, например, a₀ и называют его пустым. Его наличие в ячейке означает, что она пустая.

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

Управляющее устройство представляет собой такой механизм, который на каждом шаге вычисления находится в одном из множества состояний Q = {q₁; q₂;... q_m}; в зависимости от состояния управляющего устройства q_i и считанного символа a_j из обозреваемой ячейки информационной ленты возбуждается команда на стирание или запись символа в обозреваемую ячейку, перевод управляющего устройства в новое состояние и перемещение головки на соседнюю ячейку информационной ленты; множество состояний управляющего устройства чаще всего называют внутренней памятью машины Тьюринга; поскольку символы внутренней памяти не выводятся на информационную ленту, то множество этих символов тождественно множеству нетерминальных символов формальной грамматики; среди всех состояний управляющего устройства следует выделить q₁ – начальное состояние («старт») и q₀ – конечное состояние, («стоп»), что облегчит формализацию протоколов отдельных машин Тьюринга и последующую композицию для реализации сложных вычислений. Для формализации перемещений головки относительно информационной ленты введем дополнительный алфавит W = {R; L; S}, где R – означает перемещение головки вправо на одну ячейку информационной ленты, L – влево на одну ячейку и S – останов.

Работа машины происходит по программе, состоящей из отдельных команд. Структура команды имеет вид:

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

Построить машину Тьюринга – означает написать программу ее работы.

Машина Тьюринга останавливается только в том случае, если на очередном шаге управляющее устройство генерирует состояние q₀. Результатом работы машины Тьюринга будет заключительное слово на информационной ленте, представляющее искомый результат вычисления по заданному алгоритму.

В дальнейшем будем полагать, что алфавит машины Тьюринга состоит из двух символов {0, 1}, где 0 – пустой символ, а 1 – символ занятой ячейки. в этом алфавите любое целое неотрицательное число k представляется k+1 символами 1, записанными в соседних ячейках ленты. в этом случая число 0 будет записано так

…010…

Пример. Построить машину Тьюринга, вычисляющую функцию .

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

В ячейку, занятую аргументом x, вместо символа 1 записываем пустой символ 0. в каждом таком случае символ 1 записывается в двух ячейках, представляющих результат. Этот результат формируем в виде массива ячеек, расположенных справа от массива ячеек, занятых аргументом x, через одну пустую ячейку. Когда вместо всех ячеек, занятых аргументом x, будут только пустые ячейки, в новом массиве занятых ячеек удаляется одна ячейка с символом 1.

Программа работы машины Тьюринга, вычисляющая функцию , имеет вид:

- удалена одна занятая ячейка аргумента.

- читаются занятые ячейки аргумента.

- найдена разделяющая пустая ячейка.

- читаются занятые ячейки результата.

- заполнена одна пустая ячейка результата.

- заполнена вторая ячейка результата.

- просматриваются в обратном порядке занятые ячейки результата.

- найдена пустая разделяющая ячейка.

- найдена вторая пустая ячейка.

- снова читается пустая разделительная ячейка.

- удаляется один занятый символ. Конец.

- найдена занятая ячейка аргумента.

- просматриваются в обратном порядке занятые ячейки аргумента.

- найдена пустая ячейка перед занятыми ячейками аргумента.