Машины Тьюринга и их варианты

Данный материал ориентирован на студентов, изучающих элементы теории алгоритмов, например, в курсе  "Математической логики". Он посвящён рассмотрению вопросов существования ограниченных вариантов машин Тьюринга (МТ), способных эмулировать вычисления MT в их авторской (классической) версии.

Программа классической МТ может быть представлена конечным множеством пятёрок вида: < qi,Sj,Sk,D,ql >, где i=1,...,n; j,k=0,...,m; l=0,...,n;  D - элемент множества {L,R,N}.

Любая такая пятёрка < qi,Sj,Sk,D,ql > - это отдельная команда МТ, которая интерпретируется следующим образом.

Если в некотором такте своей работы, МТ находится в состоянии qi и обозревает символ Sj, то в этом же такте, машина одновременно выполняет три действия:

  • записывает в текущую ячейку ленты вместо символа Sj символ Sk (в частности, возможно k=j, т.е. обозреваемый символ может остаться неизменным);
  • сдвигает головку в соседнюю ячейку влево (если D= L), вправо (если D= R), или оставляет её на месте (если D= N);
  • переходит в состояние ql (в частности, возможно l=i , т.е. текущее состояние может остаться неизменным).

Из всех возможных символов, которые могут быть записаны на ленту, будем через S0 обозначать пустой символ, не отличая его при этом от содержимого пустых ячеек, т.е. тех ячеек, в которые ещё ничего не вписывалось.

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

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

Машины Поста (или Q-машины)  получатся, если в любой команде запретить записывать новый символ и сдвигать головку одновременно. Программа машины Поста состоит, таким образом,  из четвёрок вида:    < qi,Sj,Sk,ql > (возможна запись, но не сдвиг),  или < qi,Sj, D,ql > (возможен сдвиг, но не запись).

S-машины - это ограниченные МТ, которым запрещено в любом такте сдвигать головку и переходить в новое состояние одновременно. Программа S-машины строится из четвёрок вида < qi,Sj,Sk,ql > (возможен переход в новое состояние, но не сдвиг),  или < qi,Sj,Sk, D > (возможен сдвиг, но не переход в новое состояние).

D-машины - это ограниченные МТ, которым запрещено в любом такте записывать новый символ и переходить в новое состояние одновременно. Программа D-машины состоит из четвёрок вида < qi,Sj,Sk, D > (возможна запись нового символа, но не переход в новое состояние), или < qi,Sj, D,ql > (возможен переход в новое состояние, но не запись нового символа).

U-машины представляют собой самый ограниченный вариант классических МТ, который получается при запрете  выполнения в одном такте любых двух действий  одновременно. Программа U-машины состоит из троек  вида < qi,Sj,Sk> (записать новый символ, сохранив положение головки и состояние),   < qi,Sj, D > (сдвинуть головку, сохранив состояние и символ),  или < qi,Sj, ql > (сменить только состояние, сохранив при этом текущий символ и положение головки).

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

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

Пример изображения конфигурации МТq3S0**S0*001*S0

В выше указанном примере изображена конфигурация МТ, при которой эта машина, находясь в состоянии  q3, обозревает 6-й по счёту символ (0), записанного на её ленте слова  **S0*001* . Как слева, так и справа от этого слова, на ленте предполагается наличие бесконечных последовательностей пустых символов.

Из всех возможных конфигураций МТ, особо будем выделять начальную конфигурацию (НК), стартуя с которой МТ начинает процесс переработки включённого в эту конфигурацию исходного слова и заключительную конфигурацию (ЗК), которая обязательно должна включать заключительное состояние  и содержит слово, интерпретируемое как результат этой переработки. Заметим, что ЗК может и не существовать, что случится, если состояние q0 никогда не будет достигнуто и процесс переработки входного слова будет длиться вечно. 

В качестве начальной конфигурации, для удобства, мы будем выбирать такую, при которой в состоянии q1  обозревается самый левый непустой символ входного слова (при наличии такого символа). Такую начальную конфигурацию мы будем называть стандартной.

Эмуляция машин Тьюринга.

Пусть дана некоторая МТ  Т и другая, возможно, ограниченная, МТ  T', такие, что множество символов и множество состояний  машины T содержатся, соответственно, во множестве символов и множестве состояний  машины  T'.

Будем говорить, что машина  T' эмулирует (моделирует) машину Т (т.е. представляет собой её эмулятор), если для любой начальной конфигурации Kstart машины T, машина Т', так же начав с этой конфигурации Kstart  как с исходной, в конце концов обязательно остановится в некоторой заключительной конфигурации Kstop тогда и только тогда, когда начав с Kstart, через конечное число шагов, в той же заключительной конфигурации  Kstop обязательно остановится и исходная машина T.

Ниже представлены схемы покомандной эмуляции языка классических МТ в заведомо имеющих более низкий уровень языках  Q-, S-, D- и U- машин. Эти схемы можно рассматривать как схемы построения соответствующих компиляторов с языка классической МТ на указанные низкоуровневые языки

Итак, пусть дана произвольная пятёрка (комада)  < qi,Sj,Sk,D,ql >  программы произвольной классической МТ. Распишем последовательности эмулирующих её команд для различных вариантов ограниченных МТ.

Эмулирующая последовательность машины Поста (схема Q-компиляции):

 < qi,Sj,Sk,ql,D >,   < ql,D,Sk,D,ql >;

Т.е. в общем случае, каждая команда исходной МТ должна быть представлена последовательностью двух команд эмулирующей Q-машины с расширенным (по отношению к исходной МТ) множеством её состояний.

Эмулирующая последовательность S-машины (схема S-компиляции):

 < qi,Sj,Sk,D, ql >,  < ql,Sk,D, Sk, D>;

Т.е. в общем случае, каждая команда исходной МТ должна быть представлена последовательностью двух команд эмулирующей S-машины с расширенным (по отношению к исходной МТ) множеством её символов.

 Эмулирующая последовательность D-машины (схема D-компиляции):

< qi, Sj, Sk,l,D >,    < qi, Sk,l,D , D, qD- (1) ,    < qD- ,Sp , Sp,* , D- >  (2) ,   < qD- , Sk,l,D  ,  ql,*> ,   

< ql,* , Sk,l,D , Sk , D (3) ,    < ql,* ,  Sp,* ,  Sp  > ,   < ql,* ,  Sp ,  ql  >

Т.е. в общем случае, каждая команда исходной МТ должна быть представлена последовательностью из 7 команд эмулирующей D-машины с расширенным (по отношению к исходной МТ) множеством как её символов. так и состояний. Заметим, что здесь использовано обозначение D- , которое означает "направление, противоположное D" (т.е.  D- = L, при D = R и D- = R, при D = L).

 Эмулирующая последовательность U-машины (схема U-компиляции):

Т.к. U-язык - самый низкоуровневый из рассматриваемых в данной статье, для упрощения записей, изменим подход к построению эмулирующей последовательности. А именно, будем эмулировать не исходную МТ, а уже построенную, эмулирующую её D-машину (см. выше). Действительно, из анализа эмулирующего кода D-машины видно, что 4 из 7 команд уже являются готовыми U-командами, т.к. представлены тройками. В дальнейшей детализации нуждаются только пронумерованные команды (1,2,3). Распишем U-представление этих команд.

 < qi, Sk,l,D , D, qD- >  (1) :  < qi, Sk,l,D ,  qD-,* > ,   < qD-,* , Sk,l,D , D > ,  < qD-,* , Sp ,  qD- > ;

 < qD- ,Sp , Sp,* , D->  (2):  < qD- ,Sp , Sp,*  > ,  < qD- ,  Sp,* , D- > ;

 < ql,* ,Sk,l,D , Sk ,D >  (3):  < ql,* , Sk,l,D ,  ql,*,D > ,  <ql,*,D , Sk,l,D , Sk > ,  <ql,*,D , Sk, D > , <ql,*,D ,Sp,*  ,  ql,*>

5
Your rating: Нет Average: 5 (2 votes)

Комментарии

Мне бы очень хотелось

Мне бы очень хотелось обсудить некоторые задачи из прошлой домашней работы. Привожу здесь свои решения. Хотелось бы узнать правильны ли они, можно ли упростить.

1. f(x, y) = |x - y|

  s0 1 *
q1 - *Rq2 -
q2 Rq3 R -
q3 Lq4 R -
q4 - *Lq5 -
q5 Rq6 L -
q6 R s0Lq7 s0Lq10
q7 L s0Rq6 s0Rq8
q8 R 1q9 -
q9 1R R 1q0
q10 L L 1q0

2. Унарная разность x - y =  x - y, если x>=y

                                               0, иначе

Решить нужно было в унарной СС.

  s0 1 *
q1 - *Rq2 -
q2 Rq3 R -
q3 Lq4 R -
q4 - *Lq5 -
q5 Rq6 L -
q6 R s0Lq7 s0Lq8
q7 L s0Rq6 s0Rq10
q8 L Rq9 1q0
q9 1L L 1q0
q10 R s0R 1q0

3. Дано слово в алфавите {0, 1}. Выяснить, является ли оно палиндромом. Если да, то на ленте оставить 11. Если нет, то 1.

  s0 1 0
q1 1Rq7 s0Rq2 s0Rq3
q2 Lq4 R R
q3 Lq5 R R
q4 1Rq7 s0Lq6 s0Lq7
q5 1Rq7 s0Lq7 s0Lq6
q6 Rq1 L L
q7 1q0 s0L s0L

Читаю статью и никак не могу

Читаю статью и никак не могу понять, зачем нужна такая длинная эмулирующая последовательность D-машины.
Почему нельзя ограничиться последовательностью: < qi, sj, ql >, < ql, sj, sk, D > либо < qi, sj, sk >, < qi, sk, D, ql > ?

Можно ли эмулирующую последовательность машины Поста заменить на < qi,Sj,Sk,ql >,   < ql,Sk,D > ?

И т.п. Имеет ли это принципиальное значение?

Я посмотрел все 3 МТ -

Я посмотрел все 3 МТ - ошибок, похоже, нет.
Можно ли упростить? Без фактического построения трудно сказать. Если да, то на мой взгляд, незначительно, т.к. не вижу принципиально иных алгоритмов.

Эмуляция предполагает

Эмуляция предполагает введения дополнительных промежуточных команд, которые не должны мешать основным. В частности, в любой ситуации < cостояние-символ> должна запускаться ровно одна команда - либо начинающая некоторую эмулирующую цепочку (если < cостояние-символ> соответствуют команде исходной машине), либо продолжающая такую цепочку (тогда cостояние и/или символ должны быть дополнительными, а пара < cостояние-символ> имеет смысл только для эмулирующей машины).

Рассмотрим Ваше последнее предложение о замене.
Пусть необходимо эмулировать < qi,Sj,Sk, R, ql >. И, пусть эмулируемая МТ помимо этой команды, имеет в своём составе команду < ql,Sk,Sp,L,qs > (1).

Ваши две эмулирующие команды в этом случае будут иметь вид: < qi,Sj,Sk,ql >(2), < ql,Sk,R >(3).
Возникает вопрос, что делать эмулирующей машине после выполнения первой из этих двух эмулирующих команд (т.е. команды 2) - продолжать эмуляцию командой (3) или начать эмуляцию новой команды (1) исходной машины? Ведь сложившейся ситуации < ql,Sk> соответствуют обе команды (1,3). Т.е. нарушается фундаментальное свойство детерминированности алгоритма, реализуемого данной Q-машиной. Чтобы такого не допускать, для эмулирующей МТ приходится вводить особые состояния и/или символы.

В.Ш., Вы как-то упомянули на

В.Ш., Вы как-то упомянули на лекции, что можно было бы реализовать задачу x mod 10 с помощью рекурсии. Было интересно реализовать ее, используя только рекурсию и функцию succ(x). Посмотрите, пожалуйста. Вот ссылка

Нашла в сети статью Алана

Нашла в сети статью Алана Тьюринга "Могут ли машины мыслить?". Думаю, стоит почитать.

Cпасибо, за интересную ссылку, Наташа!

Cпасибо, за интересную ссылку, Наташа!
В очередной раз.

Малхожева Оксана аватар

я тоже прочитала статью,предложенную Наташей)))

интересно,заставляет задуматься))))))