Решение.

Задание 1.Найти результат применения машины Тьюринга к записи на ленте.

 

1) q₁1→q₁1R

q₁0→q₂1L

q₂1→q₂1L

q₂0→q₀0R.

K:01111 10

_q1

2) q₁1→q₁1R

q₁0→q₂1L

q₂1→q₂1L

q₂0→q₀0R.

K:01101 0

_q1

3) q₁1→q₁1R

q₁0→q₂1L

q₂1→q₂1L

q₂0→q₀0R.

K:0 1 0000110

_q1

4) q₁1→q₁1R

q₁0→q₂1L

q₂1→q₂1L

q₂0→q₀0R.

K:01 11010

_q1

5) q₁1→q₁1R

q₁0→q₂0R

q₂1→q₃1R

q₂0→q₂0R

q₃1→q₃1R

q₃0→q₀0.

K:1 11001

_q1

 

 

6) q₁1→q₁1R

q₁0→q₂0R

q₂1→q₃1R

q₂0→q₂0R

q₃1→q₃1 R

q₃0→q₀0.

K:1 1001101

_q1

7) q₁1→q₁1R

q₁0→q₂0R

q₂1→q₃1R

q₂0→q₂0R

q₃1→q₃1 R

q₃0→q₀0.

K:1 00001

_q1

 

 

8) q₁1→q₁1R

q₁0→q₂0R

q₂1→q₃1R

q₂0→q₂0R

q₃1→q₃1 R

q₃0→q₀0.

K:1 10011

_q1

9) q₁1→q₂1R

q₁0→q₁0R

q₂1→q₁0R

q₂0→q₃0L

q₃1→q₂1L

q₃0→q₀0.

K:1 11101

_q1

 

10) q₁1→q₂1R

q₁0→q₁0R

q₂1→q₁0R

q₂0→q₃0L

q₃1→q₂1L

q₃0→q₀0.

K:1 1111

_q1

 

 

11) q₁1→q₂1R

q₁0→q₁0R

q₂1→q₁0R

q₂0→q₃0L

q₃1→q₂1L

q₃0→q₀0.

K:110101

_q1

 

12) q₁1→q₂1R

q₁0→q₁0R

q₂1→q₁0R

q₂0→q₃0L

q₃1→q₂1L

q₃0→q₀0.

K:110011

_q1

 

 

13) q₁1→q₀1

q₁0→q₂0R

q₂1→q₂1R

q₂0→q₀1.

K:01110

_q1

 

 

14) q₁1→q₀1

q₁0→q₂0R

q₂1→q₂1R

q₂0→q₀1.

K:011010

_q1

 

 

15) q₁1→q₀1

q₁0→q₂0R

q₂1→q₂1R

q₂0→q₀1.

K:0111110

_q1

 

16) q₁1→q₀1

q₁0→q₂0R

q₂1→q₂1R

q₂0→q₀1.

K:0110110

_q1

 

17) q₁1→q₁1R

q₁0→q₂0L

q₂1→q₂1L

q₂0→q₀0.

K:110011

_q1

 

18) q₁1→q₁1R

q₁0→q₂0L

q₂1→q₂1L

q₂0→q₀0.

K:110101

_q1

 

19) q₁1→q₁1R

q₁0→q₂0L

q₂1→q₂1L

q₂0→q₀0.

K:111101

_q1

 

20) q₁1→q₁1R

q₁0→q₂0L

q₂1→q₂1L

q₂0→q₀0.

K:11111

_q1

2. Построить машину Тьюринга, правильно вычисляющую функцию.

1. ¦(x) =
2. ¦(x) = 2^x-1
3. 
4. 
5. ¦(x) =
6. 
7. 
8. 
9. 
10. 
11. 
12. 
13. 
14. 
15. 
16. 
17. 
18. 
19. 
20. 

 

3.Найти функцию ¦(x,y), получаемые из с помощью операции примитивной рекурсии.

ОПРЕДЕЛЕНИЕ.Говорят, что (n+1)- местная функция φ получена из n-местной функции f и (n+2)-местной функции g с помощью оператора примитивной рекурсии, если для любых х₁,…,х_n, усправедливы равенства:

φ (x₁,…,x_n)

φ(x₁…x_n, y+1)= g(x₁…x_n,y))

 

Здесь важно отметить то, что независимо от числа аргументов в φ , рекурсия ведется только по одной переменной У ; остальные n переменных х₁,…,х_n, на момент применения схемы примитивной рекурсии зафиксированы и играют роль параметров. Кроме того , схема примитивной рекурсии выражает каждое значение определяемой функции φ не только через данные функции f и g , но и через так называемые предыдущие значения определяемой функции φ прежде чем получить значение φ(х₁,…,х_n, k),придется проделать k+1 вычисление по указанной схеме- для У=0,1,…,k.