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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

18
§ 5. Задачи и упражнения для самостоятельного решения
1. Выяснить, применима ли машина Тьюринга, задаваемая программой в
алфавите {
L
, 1}
L
1
1
q
L
П
2
q 1 П
1
q
2
q
L
П
3
q 1 Л
1
q
3
q
L
Н
0
q 1 Л
2
q
к слову Р: 1) Р = 1
3
0
2
1
2
; 2) Р = 1
3
0 1
3
; 3) Р = 1[01]
2
1. Если применима,
то найти результат применения МТ к слову Р.
Ответ: в случаях 1), 3) – машина Тьюринга применима, в 2) – машина
Тьюринга не применима.
2. По заданной машине Тьюринга и начальной конфигурации К
1
найти за-
ключительную конфигурацию.
Т
1
Т
2
L
1
L
1
1
q
L
Н
0
q 1 П
2
q
1
q
L
Н
0
q
L
П
2
q
2
q 1 Л
0
q
L
П q
3
2
q
L
П
1
q 1 Л
2
q
q
3
1 Л
1
q
L
П
1
q
1) К
1
= 1
1
q
1
5
; 1) К
1
= 1
2
1
q
1
3
01;
2) К
1
=
1
q 1
3
01; 2) К
1
= 1
1
q 1
4
.
3) К
1
= 10
1
q
1
4
;
Ответ: 1) 1
2
0
2
1
0
q 01; 2) [10]
2
0
0
q 1
2
.
3. Построить машину Тьюринга, которая применима ко всем словам в ал-
фавите {L, a, b} и делает следующее: любое слово
n
xxx ...
21
, где ax
i
=
или
bx
i
=
, ni ,1= , преобразует в слово
213
... xxxx
n
. 
          § 5. Задачи и упражнения для самостоятельного решения

1. Выяснить, применима ли машина Тьюринга, задаваемая программой в
алфавите { � , 1}

                                       �                          1

                  q1                  � П q2                 1 П q1

                 q2                 � П q3                   1 Л q1

                  q3                � Н q0                   1 Л q2


к слову Р: 1) Р = 13 02 12; 2) Р = 13 0 13; 3) Р = 1[01]2 1. Если применима,
то найти результат применения МТ к слову Р.

Ответ: в случаях 1), 3) – машина Тьюринга применима, в 2) – машина
Тьюринга не применима.

2. По заданной машине Тьюринга и начальной конфигурации К1 найти за-
ключительную конфигурацию.
                 Т1                                                    Т2

                  �             1                                           �         1

     q1        � Н q0        1 П q2                          q1       � Н q0        � П q2

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

     q3         1 Л q1       � П q1


  1) К1 = 1 q1 15;                                           1) К1 = 12 q1 13 01;
  2) К1 = q1 13 01;                                          2) К1 = 1 q1 14.
  3) К1 = 10 q1 14;
Ответ: 1) 12 02 1 q 0 01; 2) [10]2 0 q 0 12.

3. Построить машину Тьюринга, которая применима ко всем словам в ал-
фавите {�, a, b} и делает следующее: любое слово x1 x2 ...xn , где xi � a или
xi � b , i � 1, n , преобразует в слово x3 ...x n x1 x 2 .
                                               18

Страницы