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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

23
Замечание. Все арифметические операции представляют собой вы-
числимые по Тьюрингу функции.
§ 3. Задачи и упражнения для самостоятельного решения
1. Построить машину Тьюринга, вычисляющую нуль-функцию 0 (x) = 0
в алфавите {L, 1}.
Указание: Взять множество
Q
= {
0
q ,
1
q }, подставить вместо всех
единиц L, а когда встретиться символ L, то подставить символ 1.
2. Вычисляет ли МТ в алфавите {L,1 }
1) с программой
q
1
q
2
q
3
L
1 Л
2
q
L П
0
q
L Н
0
q
1
1 Н
3
q
L Л
3
q
функцию
î
í
ì
¹
=
=
.0 если ,0
,0 если ,1
x
x
xsign
2) с программой
q
1
q
2
q
3
q
4
L
L Л
2
q
L П
0
q
L П
4
q L П
4
q
1
1 Л
3
q
L Л
3
q 1 Н
0
q
функцию
î
í
ì
¹
=
=
.0 если ,1
,0 если ,0
x
x
xsign 
      Замечание. Все арифметические операции представляют собой вы-
числимые по Тьюрингу функции.

       § 3. Задачи и упражнения для самостоятельного решения

      1. Построить машину Тьюринга, вычисляющую нуль-функцию 0 (x) = 0
в алфавите {�, 1}.
      Указание: Взять множество Q = { q 0 , q1 }, подставить вместо всех

единиц �, а когда встретиться символ �, то подставить символ 1.
      2. Вычисляет ли МТ в алфавите {�,1 }
   1) с программой
                                      q1                 q2              q3

                         �          1 Л q2             � П q0          � Н q0

                         1                             1 Н q3          � Л q3




                 �1, если x � 0,
функцию sign x � �
                 �0, если x � 0.



   2) с программой
                               q1                 q2              q3              q4

                     �       � Л q2          � П q0             � П q4          � П q4

                     1                          1 Л q3          � Л q3          1 Н q0




                 �0, если x � 0,
функцию sign x � �
                 �1, если x � 0.



                                           23

Страницы