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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

17
Операторную запись алгоритма представляет собой строку, состоя-
щую из символов, обозначающих машины, символов перехода (вида |
k
q' и
k
q"|), а также символов
a
и
w
, служащих для обозначения соответственно
начала и окончания работы алгоритма. В операторной записи (некоторого
алгоритма) выражение Т
i
|
k
i
q
0
Т
j
…T
m
k
n
q
1
| T
n
обозначает разветвление ма-
шин Т
j
и T
n
, управляемое машиной Т
i
, причем заключительное состояние
0i
q машины Т
i
заменяется начальным состоянием
1n
q машины T
n
, а всякое
другое заключительное состояние машины Т
i
заменяется начальным со-
стоянием машины Т
j
(одним и тем же). Если машина Т
i
имеет одно заклю-
чительное состояние, то символы |
0i
q и
1n
q |служат для обозначения безус-
ловного перехода. Там, где могут возникнуть недоразумения, символы
0i
q
и
1n
q опускаются.
Пример 4. Операторная схема
2
|
1
|Т
1
a Т
2
|
1
20
q Т
3
|
2
30
q Т
4
w
описывает следующий «процесс вычисления». Начинает работу машина
Т
2
.
Если она заканчивает работу в состоянии
20
q , то начинает работать
машина Т
1
, а по окончании работы Т
1
вновь «выполняет работу» машина
Т
2
. Если же машина Т
2
останавливается в некотором заключительном со-
стоянии, отличном от
20
q , то работу продолжает машина Т
3
. Если Т
3
при-
ходит в заключительное состояние
30
q , то начинает работу машина Т
1
; ес-
ли же Т
3
заканчивает работу в некотором заключительном состоянии, от-
личном от
30
q , то работу продолжает машина Т
4
. Если машина Т
4
когда-
либо остановится, то процесс вычисления на этом заканчивается. 
     Операторную запись алгоритма представляет собой строку, состоя-
щую из символов, обозначающих машины, символов перехода (вида | q' и
                                                                       k

q" |), а также символов � и � , служащих для обозначения соответственно
k

начала и окончания работы алгоритма. В операторной записи (некоторого
алгоритма) выражение Тi | qi 0 Тj …Tm qn1 | Tn обозначает разветвление ма-
                             k                  k

шин Тj и Tn, управляемое машиной Тi, причем заключительное состояние

qi 0 машины Тi заменяется начальным состоянием qn1 машины Tn, а всякое
другое заключительное состояние машины Тi заменяется начальным со-
стоянием машины Тj (одним и тем же). Если машина Тi имеет одно заклю-

чительное состояние, то символы | qi 0 и qn1 |служат для обозначения безус-
ловного перехода. Там, где могут возникнуть недоразумения, символы

qi 0 и qn1 опускаются.
     Пример 4. Операторная схема


                             |       |Т1 � Т2 | q20 Т3 | q30 Т4 �
                         2       1                  1    2
описывает следующий «процесс вычисления». Начинает работу машина
Т2. Если она заканчивает работу в состоянии q20 , то начинает работать
машина Т1, а по окончании работы Т1 вновь «выполняет работу» машина
Т2. Если же машина Т2 останавливается в некотором заключительном со-
стоянии, отличном от q20 , то работу продолжает машина Т3. Если Т3 при-
ходит в заключительное состояние q30 , то начинает работу машина Т1; ес-
ли же Т3 заканчивает работу в некотором заключительном состоянии, от-
личном от q30 , то работу продолжает машина Т4. Если машина Т4 когда-
либо остановится, то процесс вычисления на этом заканчивается.


                                           17

Страницы