Дискретная математика. Элементы теории, задачи и упражнения. Часть 2. Булгакова И.Н. - 72 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

72
Решение. Пусть внешним алфавитом данной МТ является множест-
во
{
}
1,A
L
=
. Число
N
x
Î
на ленте машины записывать в виде набора из
x
единиц:
¯
L
1 1 1 … 1 1
L
1
q
Программа МТ выглядит следующим образом:
,qНq
,qПq
01
11
1
11
®L
согласно которой для любой начальной конфигурации, когда считывающая
головка обозревает одну из единиц, в каждый момент эта единица остается
на месте, и головка сдвигается вправо на одну ячейку. Этот процесс про-
должается до тех пор, пока головка не выйдет на пустую ячейку. Тогда в
пустую ячейку записывается единица, головка остается на месте. Машина
перейдет в состояние
0
q .
Можно показать, что все арифметические функции натурального ар-
гумента вычислимы по Тьюрингу. Например, работа МТ в алфавите
{
}
1,
L
при вычислении числовой функции
(
)
yxy,xf
+
=
можно описать сле-
дующей программой
1
q
2
q
3
q
4
q
L
2
1 qП
3
qЛ
L
1
1
1 qП
2
1 qП
4
qЛ
L
0
qЛ
L
Любое натуральное число
m
кодируется набором из
1
+
m
единиц; этот на-
бор обозначается через
1
1
+m
. Так,
43
1111131111211110
=
=
~,~,~,~ и т. д.
Числовая функция
(
)
n
x...,,x,xf
21
называется вычислимой по Тью-
рингу, если существует МТ такая, что для любых
n
m...,,m,m
21
если при
nn
mx...,,mx,mx
=
=
=
2211
имеем
(
)
mm...,,m,mf
n
=
21
, эта машина при-
менима к слову
111
121
1
1
1
+++ mmm
&...&& , (2)
и в заключительной конфигурации на некотором участке ленты будет за-
писано слово
1
1
+m
, а остальные ячейки окажутся пустыми. Если значение
функции
(
)
n
m...,,m,mf
21
не определено, эта МТ не применима к слову
(2). 
     Решение. Пусть внешним алфавитом данной МТ является множест-
во A � �� , 1�. Число x � N на ленте машины записывать в виде набора из
x единиц:

                    �
           �        1         1        1          …          1     1        �
                    q1

       Программа МТ выглядит следующим образом:
                            q1 1 � 1 П q1 ,
                             q1 � � 1 Н q0 ,
согласно которой для любой начальной конфигурации, когда считывающая
головка обозревает одну из единиц, в каждый момент эта единица остается
на месте, и головка сдвигается вправо на одну ячейку. Этот процесс про-
должается до тех пор, пока головка не выйдет на пустую ячейку. Тогда в
пустую ячейку записывается единица, головка остается на месте. Машина
перейдет в состояние q0 .

     Можно показать, что все арифметические функции натурального ар-
гумента вычислимы по Тьюрингу. Например, работа МТ в алфавите �� , 1�
при вычислении числовой функции f � x , y � � x � y можно описать сле-
дующей программой

                                  q1         q2         q3         q4
                      �      1 П q2        � Л q3
                      1      1 П q1        1 П q2     � Л q4     � Л q0

Любое натуральное число m кодируется набором из m � 1 единиц; этот на-
бор обозначается через 1m �1 . Так, 0 ~ 1, 1 ~ 11, 2 ~ 111 � 13 , 3 ~ 1111 � 14 и т. д.

       Числовая функция f � x1 , x 2 , ..., x n � называется вычислимой по Тью-
рингу, если существует МТ такая, что для любых m1 , m 2 , ..., m n если при
 x1 � m1 , x 2 � m 2 , ..., x n � m n имеем f �m1 , m 2 , ..., m n � � m , эта машина при-
менима к слову
                                          1m1 �1 & 1m2 �1 & ... & 1m1 �1 ,             (2)
и в заключительной конфигурации на некотором участке ленты будет за-
писано слово 1m �1 , а остальные ячейки окажутся пустыми. Если значение
функции f �m1 , m 2 , ..., m n � не определено, эта МТ не применима к слову
(2).

                                             72

Страницы