Машина Тьюринга (МТ)

Принципы, положенные в основу функционирования машинных алгоритмов.

1) Однопроцессорность и поэтому последовательная работа процессора только над одним потоком команд.

2) Управление процессора происходит под действием внешних либо внутренних событий.

3) Алгоритм понимается как последовательность переходов из состояния в состояние под действием команд или последовательностей команд.

4) Управляющие внутренние события воспринимаются как изменения в памяти процессора.

1. Машина состояний (State Machine) – SM.

SM = < S, E, П, P >

а) S = { s ₀, s ₁, …, s_k } – алфавит состояний, s ₀ – начальное состояние, s_k – конечное состояние.

б) E = { e ₁, e ₂, …, e_n } – алфавит событий (events), событие идентифицируется (происходит, совершается) при изменении состояния машины под воздействием команд.

в) П = { П ₁, П ₂, …, П _е} – набор элементарных действий, изменяющих состояние машины.

г) P ={ р ₁, р ₂, …, р_m } – набор правил (команд машины); где вид правила (команда SM) – р = { S (t), e (t), П (t) ® S (t + 1)}.

Интерпретация правил SM: если SM находится в момент времени t в состоянии S (t), идентифицируется событие e (t), тогда инициируется действие П (t), которое переводит SM в новое состояние S (t +1); момент времени «t» называется тактом работы SM. В большинстве SM употребляется другой вид правил: р = { S (t), e (t), ® S (t + 1), П (t + 1)} – с интерпретацией: событие e (t) вызывает переход в S (t + 1) и действие П (t + 1) в этот же момент.

Последовательность действий SM, приводящих SM из состояния S ₀ в конечное состояние S_k, называется алгоритмом (программой) работы SM.

Исходная информация (данные), промежуточная и результирующая (когда SM попадает в конечное состояние S_k и останавливается) записывается в память SM.

Для абстрактных SM (например, машины Тьюринга) память имеет вид ленты или строки (например, нормального алгоритма Маркова) с определенными свойствами.

МТ = < S, E, П, P > определяется как некоторая SM.

а) S – алфавит состояний.

б) E º А ={ a ₁, a _2,…, a_n } – алфавит внешних символов, которые записываются в память (на ленту). Идентификацию символа в момент t в МТ производит специализированный процессор, который называется «управляющей головкой» (УГ). Внешние символы являются событиями, которые управляют процессором УГ.

в) П = { L, R, stop } – алфавит действий УГ.

г) Для МТ определяется набор команд вида

, либо .

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

Обозначения в линейном списке:

L – ссылка на предыдущий элемент списка;

R – ссылка на последующий элемент списка;

Z – запись (для МТ это ячейка ленты, куда записывается

единственный символ);

* – спейсер, ограничивающий запись слова.

Строка с такой СД носит название «строка Тьюринга» – (СТ).

Пример SM в виде машины Тьюринга, порождающей слова языка L = aⁿbⁿ; A = { a, b, Æ, *} – алфавит символов ленты МТ. Структура данных – СТ; Æ – пустой символ; начальное состояние СТ – все ячейки пустые; * – спейсер может быть в любой ячейке. SM определяется следующими конструкциями.

а) S = { S_L, S_R, S_stop } – алфавит состояний; S_L – начальное состояние; состояние движения УГ влево, S_stop – конечное состояние, S_R – состояние движения УГ вправо.

б) Правила: Р ₁ = {(S_L, Æ, а, R) ® S_R }, правило читается так, если SM в состоянии S_L, считывает из элемента списка символ «Æ», то записывает символ «а», по правой ссылке R вызывается следующий элемент списка и SМ переходит в S_R.

Р ₂ = {(S_R, Æ, b, L) ® S_L }; P ₃ = {(S_R, a, a, R) ® S_R }

P ₄ = {(S_R, b, b, R) ® S_R }; P ₅ = {(S_L, *, *, stop) ® S_R }

P ₆ = {(S_L, b, b, L) ® S_L}; P ₇ = (S_L, a, a, L) ® S_L }.

Правила работы SM могут быть записаны в виде матриц S ´ S (матрица состояние/состояние) S ´ A (матрица состояние/собы-тие). Такая запись называется матричной структурой алгоритма (МСА). Для рассматриваемого примера:

в) Матрица переходов –S´S(состояние/состояние).

	S_L	S_R	S_stop
S_L	a,(a, L) b,(b, L)	(a, R) Æ	,(, stop)
S_R	(b, L) Æ	a,(a, R) b,(b, R)

г) Матрица – S´ A (состояние/событие).

	a	b	Æ	*
S_L	(a, L)® S_L	(b, L)® S_L	(a, R)® S_R	,(, stop)® S_stop
S_R	(a, R)® S_R	(b, R)® S_R	(b, L)® S_L

Каждое действие в правилах можно назвать элементарной программой. Набор элементарных программ П = { П ₁= (a,R); П ₂= (b,R); П ₃= (b,L); П ₄= (a,L); П_k = (*, stop)} из которых строятся сценарии работы (поведения) МТ в зависимости от начальной информации на входной ленте.

Программа работы SM может быть задана графом. Для примера на рис.1 приведен граф переходов. Вершины – состояния. Дуги помечены выражением: «если в элементе списка находится символ «х», то замени его на символ «у» и перейди к следующему элементу по ссылке L или R, в соответствии с правилом».

Рис.1 Граф переходов SM, порождающей .

Пример работы SМ со строкой Тьюринга при порождении слова а ² b ² Î L.

0) *ÆÆÆÆ 1) *Æ а ÆÆ 2) *Æ аb Æ

3) *Æ ab Æ 4) * aab Æ 5) * aab Æ

6) * aab Æ 7) * aabb 8) * aabb

9) * aabb 10)* aabb 11) Stop SM

3. Блок-схема алгоритма (БСА – машина). БСА является еще одной конструкцией алгоритмической машины, к БСА достаточно просто перейти от SM, если задан ее граф переходов.

БСА суть направленный граф с множествами вершин двух типов.

1) П – программные вершины,2) R – вершины-распознаватели. Дуги RП, RR помечаются «+» или «–», дуги ПП, ПR не помечаются. Интерпретация графа: П – программный блок, R – содержит проверку истинности или ложности условия. Проверку выполняет программа, вычисляющая соответствующий предикат.

Интерпретация работы БСА – машины.

1) Машина начинает работу с П ₀ (начальный программный блок) и заканчивает (останавливается) после работы над блоком П_k.

2) Переход после окончания работы над блоком П_i к блоку П _J безусловно (по стрелке) либо через распознаватель R по стрелке «+», если условие (предикат) распознавателя выполнено, или по стрелке «–», если условие (предикат) не выполнено. Выполнение/невыполнение условия суть события, на которые БСА реагирует включением того или иного блока.

4 Блок-схема алгоритма машины, порождающей слова языка

БСА построена по SM, приведенной в пункте 2, Æ₁, Æ₂, Æ₃, a ₁, a ₂, b ₁, b ₂ – обозначение распознавателей пустого символа и символов a, b.

Ä – останов БСА-машины при неправильной ситуации на ленте.

5 Строка Ляпунова (СЛ) представляет граф в виде слова, построенный по определенным правилами, который служит логическим «скелетом» программы. СЛ является логической моделью записи программы на любом процедурном языке для однопроцессорной алгоритмической машины.

На рисунке представлена строка Ляпунова для алгоритма порождения со структурой данных СТ.

Строка Ляпунова суть последовательность символов П, условий распознавателя, стрелок и специального символа w. Она строится по следующим правилам:

1) «+» стрелка не показывается, за ней всегда идет программный блок или символ w (безусловный переход);

2) «–» стрелка показывает переход на соответствующий программный блок;

3) после символа w стрелка показывает безусловный переход на соответствующий программный блок.

6. Эквивалентные преобразования СЛ. Символы СЛ могут быть переставлены в любой последовательности, при этом сохраняется логическая структура графа БСА.

Далее приведена «запутанная» строка Ляпунова (местами поменялись П₂и П₃).

7. Строка Маркова (СМ). Сложность алгоритма зависит от структур данных. Строка Маркова (СМ) получила свое название по имени Маркова, автора нормального алгоритма Маркова, где она была впервые использована. СМ обладает рядом свойств, которые позволяют строить очень простые порождающие и распознающие алгоритмы. Но реализация структуры данных типа СМ даже в языках программирования высокого уровня достаточно сложна. Реализация СМ должна удовлетворять некоторым условиям.

Свойства СМ, которые делают ее «резиновой» (растягивающейся/сжимающейся) при перестановках (заменах) фрагментов слов:

а) Растяжение СМ.

Правило подстановки j®y такое, что |j|<|y| (длина слова j меньше длины слова y). При выполнении подстановки строка растягивается.

Например, x = aaSbb – слово, (S ® aSb) – правило.

Применение правила дает слово x¢ = aaaSbbb.

б) Сжатие СМ.

Правило подстановки j®y такое, что |j| > y|.

Например, x = aaSbb – слово, (aSb®S) – правило; применение правила дает слово x¢ = aSb.

Пример SM, порождающей слова языка L = aⁿbⁿ, использующей структуру данных «строка Маркова» (СМ). Обратите внимание, как упрощается алгоритм по сравнению с аналогичным, но работающим со «строкой Тьюринга» (п. 2).