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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

21
Решение. Будем предполагать, что перед началом работы на ленте
машины записаны исходные значения аргумента и считывающая головка
обозревает первый слева значащий символ (см. рис. 1). Кроме того, после
выполнения вычислений считывающая головка останавливается в заклю-
чительной конфигурации.
Прежде чем приступить к написанию программы работы машины
Тьюринга, следует определить порядок ее работы для получения результата.
В нашем случае после окончания работы машины на ленте должно быть за-
нято на одну ячейку больше, чем на ней занято ячеек перед началом работы.
Команды этой машины могут быть определены следующим образом:
,11
11
Пqq
®
.1
01
Hqq
®
L
Работа машины
3
T
при вычислении
)
1
(
f
состоит из конфигураций:
¯
1 1
1
q
Рис. 1
¯
1 1
1
q
Рис. 2
¯
1 1
L
1
q
Рис. 3
¯
1 1 1
0
q
Рис. 4 
     Решение. Будем предполагать, что перед началом работы на ленте
машины записаны исходные значения аргумента и считывающая головка
обозревает первый слева значащий символ (см. рис. 1). Кроме того, после
выполнения вычислений считывающая головка останавливается в заклю-
чительной конфигурации.
     Прежде чем приступить к написанию программы работы машины
Тьюринга, следует определить порядок ее работы для получения результата.
В нашем случае после окончания работы машины на ленте должно быть за-
нято на одну ячейку больше, чем на ней занято ячеек перед началом работы.
     Команды этой машины могут быть определены следующим образом:
                              q11 � 1Пq1 , q1 � � 1Hq 0 .
     Работа машины T3 при вычислении f (1) состоит из конфигураций:
                                     �
                                     1            1
                                    q1

                                    Рис. 1
                                                  �
                                     1            1
                                                  q1

                                    Рис. 2
                                                       �
                                1             1        �
                                                       q1

                                     Рис. 3
                                                           �
                          1               1                1
                                                        q0

                                     Рис. 4

                                         21

Страницы