DMT Машина Тьюринга

Машиной Тьюринга T  =  (A,Q,p ) называется тройка, состояний из непустых конечных множеств A  =  {a₀,a₁,…, a_n}, Q  =  {q₀,q₁,…, q_m} и частичной функции
p :  Q ? A ®  Q ? A ? {L,S,R}.

Здесь {L,S,R} – множество, состоящее из трех элементов. Оно одинаково для всех машин Тьюринга и интерпретируется командами перемещения головки: L – влево, R – вправо, S – стоять на месте.

Множество А называется внешним алфавитом, его элементы – буквами. Буквы a₀ и a₁ для всех машин Тьюринга одинаковы: a₀ = 0,a₁ = 1. Элементы q₀,…, q_m называются внутренними состояниями.

Частичная функция p называется программой и записывается или с помощью прямоугольной таблицы, в которой в клетке ( q_i,q_j) записывается тройка
p ( q_i,q_j)  I  Q ? A ? {L, S, R}, или с помощью списка команд вида:

· q_ia_j  ®   q_ka_e означающей ( q_k,a_e,S) = p ( q_i,a_j),

· q_ia_j  ®   q_ka_eR означающей ( q_k,a_e,R) = p ( q_i,a_j),

· q_ia_j  ®   q_ka_eL означающей ( q_k,a_e,L) = p ( q_i,a_j).

Эти команды обозначим через T( i,j).

Машиным словом , или конфигурацией, называется слово вида: a q_ka_eb , где
 0  ?   k  ?   m,  0  ?   e  ?   n,  a и b – слова (возможно, пустые), составленные из букв алфавита А. Для обозначения слова аа…а, в котором буква а повторяется x раз, пишем: а^х.

Машинное слово: a q_ka_eb интерпретируется как положение, при котором головка указывает на символ a_e, машина находится во внутреннем состоянии q_k, слева от текущей ячейки находятся символы, составляющие слово a , а справа – слово b . В примере 1 машинное слово равно: 20q_i931 для некоторого i.

Пусть задана машина Тьюринга Т и машинное слово M  =  a q_ia_jb , где 0  ?   i  ?   m. Обозначим через M_T’ слово, которое получается (за один такт) по правилам:

1) для i  =  0 положим M_T’ = M;

2) для i  >  0 выполняем одно из следующих трех преобразований:

·          если T( i,j)  =   q_ia_j ®   q_ka_e, то M_T’ =  a q_ka_eb ;

·          в случае T( i,j)  =   q_ia_j® q_ka_eR,

если b не пусто, то M_T’ =  a q_k a_eb , иначе M_T ’=  a q_k a_e a₀;

·          в случае T( i,j)  =   q_ia_j ®   q_ka_eL,

если a  = a ₁ a_s для некоторых a ₁ и a_s , то M_T’ =  a ₁ q_ka_s a_eb ,

иначе (т.е. если a пусто) MT’= q_ka₀a_eb (дополнительная инструкция).

Положим: M_T⁰ =  M, M_T⁽ⁿ⁺¹⁾ =  (M_T^{( n)})’.

Будем говорить, что машина Т перерабатывает машинное слово М в слово М₁, если M_T^{( n)}  =  M₁ для некоторого n  ?  0. Пишем: М  ? _T M₁, если Т перерабатывает М в М₁, и при этом не используется дополнительная инструкция (из правил образования слова M_T’).

Говорим, что машина Т вычисляет частичную функцию f:  Nⁿ ®  N, если выполнены следующие условия:

·     если (x₁,…, x_n) I   Dom( f), то машина Т останавливается, т.е. перерабатывает слово q₁01^x10…1^xn0 в некоторое слово a q₀b , и при этом a q₀b содержит f(x₁,…, x_n) вхождений символа  1 (здесь символы  x₁, … , x_n   обозначены через x 1,  ..., xn ) ;

·           если (x₁,…, x_n) не принадлежит Dom( f), то машина, начиная со слова
M  = q₁01^x10…1^xn0, работает бесконечно, т.е. q₀ не входит в M_T^{( n)} ни для каких n  ?  0.

Говорим, что машина Т правильно вычисляет частичную функцию f:  Nⁿ ®  N, если выполнены условия:

·     если (x₁,…, x_n) I   Dom( f), то q₁01^x10…1^xn0 ? _T q₀01^{f(x1,…, xn)}0…0;

·     в противном случае машина, начиная со слова q₁01^x10…1^xn0, работает бесконечно.

Частичная функция f называется (правильно) вычислимой, если существует машина Тьюринга, которая (правильно) вычисляет f.

Пример 1

Пусть машина Тьюринга T  =  {A, Q, p },  A  =  {0,1},  Q  =  {q₀,q₁,q₂} задана с помощью таблицы:

Рассмотрим слово: M  =  q₁011…10. На первом шаге выполняется команда q₁0® q₂0R. Получаем: M_T’ =  0q₂11…10. Затем, до тех пор, пока слово не превратится в слово  011…1q₂0, будет выполняться команда q₂1 ®  q₂1R. После этого будет выполнена команда q₂0 ®  q₀1, и машина остановится, ибо q₀ соответствует состоянию остановки. Входное слово, состоящее из x единиц, означает, что аргументом вычисляемой функции является число x. Поскольку на выходе получается x + 1 подряд идущих единиц, то машина вычисляет функцию: s( x)  =   x + 1.

Пример 2

Вычисление функции: s( x)  =  x+1 в примере 2 не является правильным. Построим машину Тьюринга для правильного вычисления:

Программа реализующая Машину Тьюринга - MashinTuring

Работа с программой MashinTuring

Программу Машины Тьюринга необходимо записать в виде таблицы команд: aKq, где:

a   - новое содержание текущей ячейки  на ленте (0 или 1).

K  - команда лентопротяжного механизма машины Тьюринга (влево – 'L', вправо – 'R', стоп – 'S')

q - новое внутренне состояние машины Тьюринга (' Q'+целое число от 0 до n)

Для изменения содержимого ячейки информационной ленты необходимо щелкнуть правой кнопкой мыши (0) или левой (1)

 

Данная программа воспроизводит все действия используя таблицу переходов, состояний и ленту.

Регистрирует собственное расширение для своих файлов.