20. Машина Тьюринга (мт)

Из-за ограниченной внутренней памяти и отсутствия внешней КА может реализовать только узкий класс задач. Если к модели КА добавить неограниченную внешнюю память, то получим автомат, реализующий любой алгоритм. Такой автомат называется Машиной Тьюринга. МТ состоит из 2 частей: ленты и конечного автомата. Лента неподвижна, а головка движется относительно ленты под управлением автомата (влево, вправо, стоит на месте). МТ может выполнять следующие команды:

1) записывать в ячейку ленты новый символ;

2) сдвигаться на одну ячейку влево или вправо;

3) переходить в новое внутреннее состояние.

Больше МТ ничего не может. МТ задается:

1) набором внутренних состояний Q={q1…qn};

2) входным алфавитом S={s1…sk);

3) командами движения головки {L,R,N}.

4) программой управления, которую удобно задавать в табличной форме. Автомат останавливается по команде stop (!) в определенном состоянии (конфигурации) .

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

В своем вычислительном устройстве Тьюринг смоделировал доведенный до са­мых элементарных операций процесс выполнения произвольного алгоритма че­ловеком. Человек имеет конечную память, и в этом смысле его можно представить системой с конечным числом состояний. Исходная информация к алгоритму обыч­но представляется в виде цепочки символов. Можно себе представить, что эта ин­формация представлена в виде слова (конечной последовательности символов) конечного словаря. Выполняя алгоритм, человек-вычислитель использует допол­нительную память (которая может быть потенциально бесконечной, например листы бумаги) для записи информации, причем эта запись производится им по­следовательно, символ за символом. При вычислениях человек может возвращаться к ранее записанной информации, стирать некоторую информацию и т. д.

21. Формальное определение

диаграмма автомата с магазинной памятью

В отличие от обычных конечных автоматов, автомат с магазинной памятью является набором^[1]:

 где

• K — конечное множество состояний автомата

•  — единственно допустимое начальное состояние автомата

•  — множество конечных состояний, причём допустимо F=Ø, и F=K

• Σ — допустимый входной алфавит, из которого формируются строки, считываемые автоматом

• S — алфавит памяти (магазина)

•  — нулевой символ памяти.

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

Автомат с магазинной памятью может распознать любой контекстно-свободный язык.

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