Введение в схемы, автоматы и алгоритмы



             

Односторонние машины Тьюринга


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

{\cal M}\
называется односторонней, если в процессе вычисления ее головка никогда не сдвигается левее начальной ячейки (т.е. всегда находится в ячейках с положительными номерами).

Лемма 9.2. Для всякой м.Т.

\cal M
можно построить эквивалентную одностороннюю м.Т.
{\cal M}^\prime\
.

Доказательство. Пусть

\ {\cal M} = <Q, \Sigma, P,q_0, q_f>.
Будем считать (используя лемму 1 ), что
\cal M\
завершает работу в стандартных конфигурациях. Требуемая м.Т.
\ {\cal M}^\prime = <Q^\prime, \Sigma^\prime, P^\prime,q_0^\prime, q_f^\prime>\
будет моделировать работу
\cal M
, используя "многоэтажную" ленту . Содержимое ячеек на 1-ом (нижнем) этаже будет на каждом такте совпадать с содержимым тех же ячеек
\cal M
, на 2-ом этаже будет копироваться содержимое левой полуленты: на нем в i-ой ячейке
{\cal M}^\prime\

будет тот же символ, что и в -i-ой ячейке

\cal M
. Кроме того, на 3-ем этаже в 1-ой ячейке будет стоять отмечающий ее символ #. Таким образом, ?' = ? ? ? ? {
, # }
?. Работа
{\cal M}^\prime\
будет происходить следующим образом.

  1. 1) На первом этапе отмечается 1-я ячейка и содержимое входа переписывается на 1-ый этаж трехэтажной ленты:
    \ q_0^\prime a \rightarrow p_1 \left(\frac{\frac {\#}{\wedge}}{a}\right)\textit{П}\ \ (a \in \Sigma);\qquad p_1 a \rightarrow p_1 \left(\frac{\frac {\wedge}{\wedge}}{a}\right)\textit{П}\ ( a \in \Sigma \backslash \{\wedge \};\qquad p_1 \wedge \rightarrow p_2\,\wedge\, \textit{Л};\\ \ p_2 \left( \frac{\frac {\wedge}{\wedge}}{a} \right) \rightarrow p_2 \left(\frac{\frac {\wedge}{\wedge}}{a} \right)\,\textit{Л}\ \ (a \in \Sigma);\ \ p_2 \left(\frac{\frac {\#}{\wedge}}{a}\right) \rightarrow q_0 \left(\frac{\frac {\#}{\wedge}}{a}\right)\textit{Л}\ \ (a \in \Sigma).

  2. Затем

    {\cal M}^\prime\
    моделирует работу
    \cal M\
    , используя для работы на 2-ом этаже дубликаты состояний (со штрихами) и команды со сдвигами в обратном направлении. Для команды q ,a
    r , b ,C из P и для всех c
    ? в P' поместим команды:

    \ q\,\left(\frac{\frac{\wedge}{c}}{a}\right) \rightarrow\ r \left(\frac{\frac {\wedge}{c}}{b}\right)\,C\ \ \mbox{ и } q^\prime\,\left(\frac{\frac {\wedge}{a}}{c}\right) \rightarrow\ r^\prime \left(\frac{\frac {\wedge}{b}}{c}\right)\,C^\prime,\, \\ \mbox{где }C^\prime = \left\{ \begin{array}{lcl} \textit{ П }& \mbox { при } & C=\textit{Л}\\ \textit{Л }& \mbox { при } & C=\textit{П}\\ \textit{Н} & \mbox { при } & C=\textit{Н} \end{array} \right.

    Кроме того, для a =

    сохраним и старые команды для работы на впервые посещаемых ячейках:

    \ q\,\wedge \rightarrow\ r \left(\frac{\frac {\wedge}{\wedge}}{b}\right)\,C\ \mbox{ и } q^\prime\,\wedge \rightarrow\ r^\prime \left(\frac{\frac {\wedge}{b}}{\wedge}\right)\,C^\prime.

    Сдвиги

    \cal M\
    из 1-ой ячейки налево в -1-ю и обратно моделируются переходом с одного этажа на другой в 1-ой ячейке
    \cal M^\prime:

    \ q\,\left(\frac{\frac{\#}{c}}{a}\right) \rightarrow\ \overline{r} \left(\frac{\frac {\#}{c}}{b}\right)\,\overline{C}, \mbox{ где при } C=\textit{Л} \overline{r}=r^\prime, \overline{C}= \textit{Н},\\ \mbox { а при } C\neq \textit{Л}\ \ \overline{r}=r, \overline{C}= C \\ \ q^\prime\,\left(\frac{\frac{\#}{a}}{c}\right) \rightarrow\ \overline{r} \left(\frac{\frac {\#}{b}}{c}\right)\,\overline{C}, \mbox{ где при }C=\textit{П}\ \ \overline{r}=r,\ \overline{C}= \textit{Н},\\ \mbox{ а при } C\neq \textit{П}\ \ \overline{r}=r^\prime, \overline{C}= C.

  3. После завершения моделирования

    \cal M\
    результат записан в начальных ячейках на 1-ом этаже.
    \cal M^\prime\
    переводит его в первоначальный алфавит ?.

    \ q_f\,\left(\frac{\frac{c}{\wedge}}{a}\right) \rightarrow\ q_f\,a\,\textit{П} \quad (a \in \Sigma \backslash \{\wedge\},\ c \in \{\wedge, \#\}\ ), \qquad q_f\, \wedge \rightarrow\ q_f^\prime\,\wedge\, \textit{Н}.

    Проверка правильности работы м.Т.

    \cal M^\prime\
    предоставляется читателю (см. задачу 9.4).




Содержание  Назад  Вперед