Если для решения некоторой массовой
проблемы известен алгоритм, то для его реализации необходимо лишь четкое
выполнение предписаний этого алгоритма. Автоматизм, необходимый при реализации
алгоритма естественно приводит к мысли о передаче функции человека,
реализующего алгоритм, машине. Идею такой машины предложили в тридцатые годы ХХ
века американский математик Э. Пост и английский математик А. Тьюринг.
Рассмотрим один из вариантов указанной
машины, которая носит название машины
Тьюринга.
Машина Тьюринга имеет три алфавита:
1. Внешний алфавит с пустым символом – АÈ{L}.
2. Внутренний алфавит, или алфавит
состояний Q =
{q0, q1, …, qn}. состояние q0 называется заключительным состоянием, q1 – начальным состоянием, состояния q2, q3, …, qn – рабочими состояниями.
3. Алфавит сдвигов S = {-1, 0, +1}.
В конструкции машины имеются:
а) бесконечная лента (разбитая на
ячейки). В каждую ячейку может быть записана только одна буква.
б) считывающе-записывающее
устройство (СЗУ). СЗУ обладает способностью обозревать одну ячейку ленты,
считывать букву, записанную в ячейку, заносить на место считываемой буквы любую
другую из АÈ{L},
передвигаться вдоль ленты влево и вправо на одну ячейку;
в) устройство управления (УУ), которое
управляет с помощью программы машины её работой;
г) программа машины, определяющая
переходы машины от одной конфигурации к другой.
Говорят, что известна конфигурация
машины, если известны ячейка, обозреваемая СЗУ и состояние машины.
Программа машины – отображение,
сопоставляющее любой паре (а, qi ) – буква-состояние тройку: (b, qi , s) – буква-состояние-сдвиг. Программа МТ
обычно задается в виде таблицы.