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

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

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

Информационная лента бесконечной длины представляет собой последовательность ячеек, в каждую из которых записан в точности только один символ из множества символов алфавита V_T={a₁,a₂,...,a_n}. Последовательность символов на ленте формирует слово α = (a₁a₂...). Пробел между словами также является символом множества V_T. Информационная лента исполняет функции внешней памяти машины Тьюринга.

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

Управляющее устройство представляет собой механизм, который на каждом шаге вычисления находится в одном из множества состояний Q={q₁,q₂,...,q_m}. В зависимости от состояния q_i и считанного символа a_j управляющее устройство выдает команду на стирание или запись символа в обозреваемую ячейку, перевод управляющего устройства в новое состояние и перемещение головки на соседнюю ячейку информационной ленты. Поэтому состояния управляющего устройства называют «памятью машины Тьюринга», так как машина помнит все промежуточные состояния, которые привели машину из состояния q₀ (так обозначается начальное состояние) в некоторое состояние q_i. Среди всех состояний управляющего устройства, кроме начального, следует выделить также состояние q_k — конечное состояние («стоп»), что облегчит составление протоколов машин Тьюринга и композицию нескольких машин Тьюринга. Для описания перемещений головки относительно информационной ленты введем дополнительный алфавит D={П, Л, С}, где П — означает перемещение головки вправо на одну ячейку информационной ленты, Л — влево на одну ячейку и С — останов.

Работа машины Тьюринга состоит в многократном повторении следующего цикла элементарных действий:

· действие первое: считывание символа a_j, находящегося под считывающей головкой;

· действие второе: поиск команды, отвечающей текущему состоянию управляющего устройства q_i и считанному символу a_j, т.е. q_j a_j => q_i a_m D;

· действие третье: исполнение найденной команды, т.е. запись в обозреваемую ячейку символа a_m, перевод управляющего устройства в состояние q_i и перемещение головки на соседнюю ячейку информационной ленты - D.

Эти три действия представляют одну элементарную команду. Последовательность команд для реализации процесса вычисления представляют программу алгоритмического процесса или протокол машины Тьюринга. Следует отметить, что никакие две команды не могут иметь одинаковую пару текущего состояния q_i и считываемого символа a_j, т.е. пару (q_i a_j). Машина Тьюринга останавливается только в том случае, если на очередном шаге управляющее устройство генерирует состояние q_k. Результатом работы машины Тьюринга будет заключительное слово на информационной ленте.