Алгоритмы: машина Тьюринга. Граф переходов, машина состояний и блок-схема алгоритма.

Машина Тьюринга (МТ) состоит из:

1)счетной ленты разделенной на ячейки иногда ограниченной слева, но не справа

2)читающей и пишущей головки которая может читать буквы рабочего алфавита А = {a0, а1,...,аt}, стирать их и печатать.

3)лентопротяжного механизма

4)операционного исполнительного устройства, которое может находиться в одном из дискретных состояний {s0, s1,..., sk }, принадлежащих алфавиту S внутренних состояний.

 

Порядок работы МТ описывается таблицей машины Тьюринга.

Эта таблица является матрицей с четырьмя столбцами и (k + 1)(t + 1) строками.

Каждая строка имеет вид

s_i a_j v_ij s_ij, 0 <= i < k, 0 <= j <= t,

Если МТ находится в исходном состоянии s_i, то головка прочитывает символ a_j в рабочей ячейке, выполняет команду v_ij и переходит в состояние s_ij

Что такое v_ij

•r - переместить ленту вправо,

•l - переместить ленту влево,

• stop - остановить машину;

•- действие МТ, состоящее либо в занесении в ячейку ленты символа алфавита a_k , стирая при этом существующий в ячейке символ, либо в изменении

состояния s_ij

 

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

s_i a_j v_ij s_ij

Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной, (при

этом машина либо “удачлива”, либо делает копии, либо может быть вероятностной).

Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый

символ, перейти в новое состояние и переместиться на одну клетку влево или вправо.

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

 

Математическое описание МТ

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

Сложение двух чисел x и y в унарной системе, как пример порождающей МТ.

𝑨 = {𝟏, +,(,), =, 𝝋} – алфавит рабочих символов (располагаются на ленте).

𝑺 = {𝑺𝟎, 𝑺=, 𝑺+, 𝑺), 𝑺𝒌} – алфавит состояний, переход в то или иное состояние, определяет логику работы алгоритма.

Начальное состояние ленты

(11+111)

где x=11 и y=111.

УГ сдвинута (установлена) на левый спейсер «(».

Результат порождения x+y=11111.

 

Логическая схема алгоритма (ЛСА) задаётся либо матрицей переходов, либо графом:

Граф переходов МТ есть направленный бинарный граф G=<S,V>,

• S – вершины, которые соответствуют множеству состояний МТ;

• V – множество дуг, которые соответствуют переходам (правилам) из состояния 𝑺𝒊 в состояние 𝑺𝒋

каждая дуга помечается состоянием памяти a_i (символом a_i, содержащимся в ячейке ленты, на которую указывает головка) и командой П_j, которую

должна выполнить УГ в данном такте j.

Граф переходов GS замечателен тем, что он содержит все возможные «траектории» работы МТ, которые могут быть сколь угодно длинными (но конечными) и (это основное) определяет ЛСА работы МТ, начиная с

начального состояния S 0, до момента останова.

Граф GS в этом случае задаёт так называемую машину состояний.

 

ЛСА, также определяющая все возможные траектории (последовательности состояний и соответствующих команд) может быть определена и другой графовой конструкцией – блок–схемой алгоритма

Блок–схема алгоритма (БСА) представляет направленный бинарный граф G=<R,V> где R – вершины двух типов

П – соответствуют действиям, командам или программам

r – соответствуют процедурам, распознающим состояния памяти.

Каждая дуга v принадлежит V помечается либо состоянием памяти (условием перехода),

либо символом «три параллельные горизонтальные линии» безусловного перехода.