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

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

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

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

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

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

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

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

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

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

a_j q_j ® a_m q_i W;

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

Эти три действия формируют элементарный шаг алгоритмического процесса. Последовательность команд для реализации процесса вычисления формирует протокол машины Тьюринга или программу алгоритмического процесса. Построить машину Тьюринга – означает написать программу ее работы.

Следует отметить, что никакие две команды не могут иметь одинаковую пару текущего состояния q_i и считываемого символа a_j, т. е. (a_j q_i).

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