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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

16
стояние Т
2
. Предположим, что внутренние алфавиты этих машин не пе-
ресекаются. Заменим везде в программе П
1
состояние
1
0
q на состояние
2
1
q и полученную программу объединим с программой П
2
. Новая про-
грамма П определяет машину Т, которая называется композицией ма-
шин Т
1
и Т
2
(по паре состояний (
1
0
q ,
2
1
q )) и обозначается Т
1
o
Т
2
или Т
1
Т
2
.
Более подробная запись полученной машины будет выглядеть – Т =
= Т(Т
1
, Т
2
, (
1
0
q ,
2
1
q )). Внешний алфавит композиции Т
1
o
Т
2
является объ-
единением алфавитов машин Т
1
и Т
2
.
2. Пусть
0
q – некоторое заключительное состояние машины Т, а
k
q –
какое-либо состояние этой же машины Т, не являющееся заключительным.
Заменим всюду в программе П машины Т символ
0
q на
k
q . В результате
получим программу П’, которая определяет машину Т’ (
0
q ,
k
q ). Машина Т’
называется итерацией машины Т по паре состояний (
0
q ,
k
q ).
3. Пусть машины Тьюринга Т
1
, Т
2
и Т
3
задаются программами П
1
,
П
2
и П
3
соответственно. Внутренние алфавиты этих машин не пересе-
каются. Пусть
'
0
q и
''
0
q – какие-либо заключительные состояния машины
Т
1
. Заменим в программе П
1
состояние
'
0
q некоторым начальным состоя-
нием
'
1
q машины Т
2
, а состояние
''
0
q некоторым начальным состоянием
"
1
q машины Т
3
. Затем новую программу объединим с программами П
2
и
П
3
. Получим программу П, задающую машину Тьюринга
Т = Т(Т
1
(
'
0
q ,
'
1
q ),Т
2
(
''
0
q ,
"
1
q ),Т
3
), которая называется разветвлением машин
Т
2
и Т
3
, управляемым машиной Т
1
.
Отметим, что при построении сложных машин Тьюринга применяют
так называемую операторную запись алгоритма. Этот способ построения
впервые был предложен А.А. Ляпуновым в 1953 году. Так как специальный
операторный язык для записи алгоритмов носит вспомогательный характер, то
не имеет смысла давать его строгое формально-логическое определение. Ос-
тановимся на кратком описании операторного языка и рассмотрим пример. 
стояние Т2. Предположим, что внутренние алфавиты этих машин не пе-
ресекаются. Заменим везде в программе П 1 состояние q10 на состояние

q12 и полученную программу объединим с программой П2. Новая про-
грамма П определяет машину Т, которая называется композицией ма-
шин Т1 и Т2 (по паре состояний ( q10 , q12 )) и обозначается Т1 � Т2 или Т1Т2 .
Более подробная запись полученной машины будет выглядеть – Т =
= Т(Т1, Т2, ( q10 , q12 )). Внешний алфавит композиции Т1 � Т2 является объ-
единением алфавитов машин Т1 и Т2.
       2. Пусть q0 – некоторое заключительное состояние машины Т, а qk –
какое-либо состояние этой же машины Т, не являющееся заключительным.
Заменим всюду в программе П машины Т символ q0 на qk . В результате
получим программу П’, которая определяет машину Т’ ( q0 , qk ). Машина Т’
называется итерацией машины Т по паре состояний ( q0 , qk ).
        3. Пусть машины Тьюринга Т1, Т2 и Т3 задаются программами П1,
П2    и П3 соответственно. Внутренние алфавиты этих машин не пересе-
каются. Пусть q0' и q0' ' – какие-либо заключительные состояния машины
Т1. Заменим в программе П1 состояние q0' некоторым начальным состоя-
нием q1' машины Т2, а состояние q0' ' некоторым начальным состоянием
q1" машины Т3. Затем новую программу объединим с программами П 2 и
П3.     Получим      программу       П,        задающую    машину      Тьюринга
Т = Т(Т1( q0' , q1' ),Т2( q0' ' , q1" ),Т3), которая называется разветвлением машин
Т2 и Т3, управляемым машиной Т1.
      Отметим, что при построении сложных машин Тьюринга применяют
так называемую операторную запись алгоритма. Этот способ построения
впервые был предложен А.А. Ляпуновым в 1953 году. Так как специальный
операторный язык для записи алгоритмов носит вспомогательный характер, то
не имеет смысла давать его строгое формально-логическое определение. Ос-
тановимся на кратком описании операторного языка и рассмотрим пример.
                                          16

Страницы