4.2. Машины Тьюринга

 

Если для решения некоторой массовой проблемы известен алгоритм, то для его реализации необходимо лишь четкое выполнение предписаний этого алгоритма. Автоматизм, необходимый при реализации алгоритма естественно приводит к мысли о передаче функции человека, реализующего алгоритм, машине. Идею такой машины предложили в тридцатые годы ХХ века американский математик Э. Пост и английский математик А. Тьюринг.

Рассмотрим один из вариантов указанной машины, которая носит название машины Тьюринга.

Машина Тьюринга имеет три алфавита:

1. Внешний алфавит с пустым символом – АÈ{L}.

2. Внутренний алфавит, или алфавит состояний Q = {q0, q1, …, qn}. состояние q0 называется заключительным состоянием, q1 – начальным состоянием, состояния q2, q3, …, qn  – рабочими состояниями.

3. Алфавит сдвигов S = {-1, 0, +1}.

В конструкции машины имеются:

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

б) считывающе-записывающее устройство (СЗУ). СЗУ обладает способностью обозревать одну ячейку ленты, считывать букву, записанную в ячейку, заносить на место считываемой буквы любую другую из АÈ{L}, передвигаться вдоль ленты влево и вправо на одну ячейку;

в) устройство управления (УУ), которое управляет с помощью программы машины её работой;

г) программа машины, определяющая переходы машины от одной конфигурации к другой.

Говорят, что известна конфигурация машины, если известны ячейка, обозреваемая СЗУ и состояние машины.

Программа машины – отображение, сопоставляющее любой паре (а, qi ) – буква-состояние тройку: (b, qi , s) – буква-состояние-сдвиг. Программа МТ обычно задается в виде таблицы.