Произвольные автоматы и машина Тьюринга. (ТА)

Определение: МТ - это алгоритмическая модель представляющая собой некоторое идеализированное устройство. Существует наиболее распространенные 3 типа универсальных моделей:

1) детерминированные устройства: МТ, машина Поста (процедурное программирование);

2) рекурсивные функции,

3) формальные системы.

МТ состоит из 3-х частей:

1) Управляющее устройство которое может находиться в одном из состояний q_i принадлежащему конечному множеству состояний Q={q₁, q₂, …, q_n};

2) лента I - разбитая на ячейки в каждой из которых мажет быть записан один из знаков некоторого алфавита V={a₀, a₁,…, a_m}, причем лента бесконечна в обе стороны;

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

МТ функционирует следующим образом:

1) считывается некоторый знак a_j находящийся в текущей ячейке ленты. В зависимости от считываемого знака a_j и текущего состояния устройства управления q_i в ячейку ленты записывается некоторый знак a_j^|.

2) В зависимости от считанного знака a_j и текущего состояния q_i устанавливается новое текущее состояние q_i^|.

3) В зависимости от текущего считанного знака a_j и текущего состояния q_i лента перемещается в некоторое направление d_k Î D = {L,R,E}. 4) С приходом следующего дискретного момента времени (следующий такт), последовательность функционирования повторяется.

Формальное определение МТ - называется формальная система состоящая из следующих объектов (или множеств) T=<V,Q,P,I>, где V - внешний алфавит обязательно включающий e, Q- внутренний алгоритм, Q={q_z, q₁, q₂, …, q_n} (q_z - обозначает заключительное состояние). P - программа МТ является дискретной функцией отображающей декартовое произведение Q ´ V ® Q ´ V ´ D, где D -множество направлений перемещения ленты, I - начальная конфигурация МТ, это строка начинается с q_i, после которого начинается подстрока внутреннего алфавита. I = q_i a; q_i Î Q; a Î V*.

3 способа задания МТ: 1) табличный; 2) в виде ориентированного графа; 3) в виде строки знаков.

Выводы: Так как язык не пустой существует хотя бы одна МТ. Количество МТ счетно. Решима проблема распознавания правильных описаний МТ. Конфигурацией МТ называется строка следующего вида K=A₁q_iA₂, где q_i -принадлежит множеству внутренних состояний МТ, а A₁ и A₂ - строки алфавите V*. Можно выделить стандартную начальную и заключительную конфигурации: I = q₀a₂ (слева от устройства доступа находится пустая строка); z = q_zb (справа от устройства доступа находится результирующая строка).

Тезис Тьюринга: Любой алгоритм может быть реализован МТ. Если некоторую процедуру нельзя реализовать МТ, то эта процедура не алгоритм.