Структура машины Тьюринга

В качестве исполнителя алгоритмов Тьюринг предложил автомат, состоящий из:

  • — бесконечной ленты, разбитой на ячейки;
  • — головки (каретки), способной передвигаться над лентой от ячейки к ячейке, считывать символы, записанные налейте, записывать символы в ячейки.

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

  • — считать символ из ячейки, над которой каретка находится;
  • — записать символ в ячейку, над которой каретка находится;
  • — переместиться либо влево, либо вправо на следующую ячейку, либо остаться на месте;
  • — изменить свое внутреннее состояние.

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

Структурная схема машины Тьюринга

Рис. 14.1. Структурная схема машины Тьюринга

На рис. 14.1 представлена структурная схема машины Тьюринга, где обозначены:

В — внешняя память машины, которую можно интерпретировать как не ограниченную в обе стороны ленту, которая делится на элементарные ячейки;

Q — внутренняя память машины, определяющая состояния, в которых находится машина в любой момент времени;

G — считывающая (записывающая) головка;

Z — логический блок машины, формирующий символ, который будет записан на ленту, а также управляющий переходами машины из одного состояния в другое;

Р— устройство, управляющее головкой. Основные кодовые символы для управления машиной: R — движение головки вправо; L — движение головки влево; Я — продолжать обозревать текущую ячейку

Символы, записанные на ленте В, образуют внешний, или исходный, алфавит. Среди символов исходного алфавита выделяется пустой символ. Чаще всего это X. Тогда информация на ленте может иметь вид

Алфавит внутренних состояний машины задается множеством

где q0 — начальное состояние, определяющее начало алгоритма; qk конечное состояние, определяющее конец алгоритма.

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

 
Посмотреть оригинал