Машина Тьюринга и рекурсивные функции. Кацаран Т.К - 12 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

12
Решение. За внешний алфавит машины
1
T возьмем множество
}
,
,
{
b
a
A
L
=
, а за внутренний – },,,{
3210
qqqqQ
=
. Команды определим сле-
дующим образом: ,
21
Пqaq
®
,
31
Пqbq
®
ii
yППyq
®
, где
}
,
{
b
a
y
Î
,
3
,
2
=
i
;
,
02
aHqq
®
.
03
bHqq
®
Рассмотрим работу машины
1
T над словом
ba
. В работе машины над
словом
ba
начальная конфигурация имеет следующий вид:
¯
(1)
b
a
1
q
На первом шаге действует команда:
31
Пqbq
®
. В результате создается
следующая конфигурация:
¯
(2)
L
a
3
q
На втором шаге действует команда
®
aq
3
3
aПП
, и на машине создается
конфигурация
¯
(3)
L
a
L
3
q
Наконец, третий шаг обусловлен командой
03
bHqq
®
. В результате чего
создается конфигурация:
¯
(4)
L
a
b
0
q 
      Решение. За внешний алфавит машины T1 возьмем множество
A � {�, a, b} , а за внутренний – Q � {q0 , q1 , q2 , q3 } . Команды определим сле-
дующим образом: q1a � �Пq2 , q1b � �Пq3 , q i y � yППi , где y �{a, b} ,
i � 2,3 ; q 2 � � aHq 0 , q 3 � � bHq 0 .
      Рассмотрим работу машины T1 над словом ba . В работе машины над
словом ba начальная конфигурация имеет следующий вид:
                                        �

                  (1)                   b         a

                                        q1

На первом шаге действует команда: q1b � �Пq3 . В результате создается
следующая конфигурация:
                                                  �

                  (2)                   �         a

                                                  q3

На втором шаге действует команда q 3 a � aПП3 , и на машине создается
конфигурация
                                                       �

                  (3)                   �         a    �
                                                       q3


Наконец, третий шаг обусловлен командой q3� � bHq0 . В результате чего
создается конфигурация:
                                                       �

                  (4)                   �         a    b

                                                       q0


                                             12

Страницы