Варианты заданий к ргр

Задание 1. Найдите функции g и h в рекурсивной формуле для двуместной функции f(x,y), если рекурсия проводится а) по переменной x, б) по переменной y. Докажите, что функция f(x,y) принадлежит классу ПРФ.

1. f(x,y)=2x+3y²+2;

2. f(x,y)=3(x³+2y);

3. f(x,y)=2x²+3y+4;

4. f(x,y)=(2x+3)y;

5. f(x,y)=x³+4y+xy;

6. f(x,y)=2(x+3y²);

7. f(x,y)=3x³+2y²;

8. f(x,y)=x(4+3y);

9. f(x,y)=4x²+y²+1;

10. f(x,y)=3(2x³+y²)+x;

11. f(x,y)=

12. f(x,y)=

13. f(x,y)=

14. f(x,y)=4^x+y+xy

15. f(x,y)=

16. f(x,y)=

17. f(x,y)=3^y-xy+3

18. f(x,y)=

19. f(x,y)=2^xy+2x+1

20. f(x,y)=

21. f(x,y)=xy+y²+1;

22. f(x,y)=3(x+y)²+1;

23. f(x,y)=2x²+3y²;

24. f(x,y)=(x+1)²y;

25. f(x,y)=x²+(4+y)²;

26. f(x,y)=(x+2y²)²;

27. f(x,y)=(x+2)²+2y²

Задание 2. Найдите функции g и h в рекурсивной формуле для трехместной функции f(x,y,z), если рекурсия проводится а) по переменной x, б) по переменной y, в) по переменной z. Докажите, что функция f(x,y,z) принадлежит классу ПРФ.

1. f(x,y,z)=xy²z

2. f(x,y,z)=x²(y+z)

3. f(x,y,z)=x²y+ y²z

4. f(x,y,z)=x+yz

5. f(x,y,z)=2^x+y+z

6. f(x,y,z)=3^x+1+y(z+1)

7. f(x,y,z)=x(z+1)2^y

8. f(x,y,z)=xy^z

9. f(x,y,z)=z^x+y

10. f(x,y,z)=x^yz

11. f(x,y,z)=xy² +3z

12. f(x,y,z)=x²(2y+z+1)

13. f(x,y,z)=x²+ 3^yz

14. f(x,y,z)=4^x+yz

15. f(x,y,z)=(2^y+1)x+3z

16. f(x,y,z)=3^x+1+2^x(z+1)

17. f(x,y,z)=x+(z+1)2^y

18. f(x,y,z)=2xy+y^z

19. f(x,y,z)=z^x+y+4

20. f(x,y,z)=x^y+1z+1

21. f(x,y,z)=2(x+z)y²

22. f(x,y,z)=x²y+4^z+1

23. f(x,y,z)=x²y+2^yz

24. f(x,y,z)=x(z²+2)+y

25. f(x,y,z)=3^x+2y+3z

26. f(x,y,z)=2^y+1+x²z

27. f(x,y,z)=x(3^z+1)2^y

Задание 3. Пусть нормальный алгоритм Маркова в алфавите А={a, b, c, d} (А={a, b}) задан последовательностью подстановок N. Выяснить, применим ли этот нормальный алгоритм к слову .

1. N: 1)bа®аb, 2)аb®l; =baabbaab.

2. N: 1)ab®a, 2)b®l, 3)a®b; = abbbbba.

3. N: 1) baab, 2) a, 3) bb; =bbbaaa.

4. N: 1) abb, 2) babb, 3) b; =bababab.

5. N: 1)bа®аb, 2)аb®l; =abbabba.

6. N: 1)ab®a, 2)b®l, 3)a®b; = abbabba.

7. N: N: 1) baab, 2) a, 3) bb; =abbbaaab.

8. N: 1) baa, 2) bbb, 3) ab, 4)b; =abbabbab.

9. N: 1) abb, 2) babb, 3) b; =bbbaaab.

10. N: 1) bbba, 2) baa, 3) a, 4)b; =abbabbab.

11. N: 1)bd®b, 2)сd®bd, 3)db®l, 4)b®dcb; =dabdc.

12. N: 1)aс®сaa, 2)dс®сbd, 3)da®l, 4)a®dca; = abaa.

13. N: 1) dccad, 2) db, 3) bdcb; =bbab.

14. N: 1)aс®сaa, 2)dс®сbd, 3)da®l, 4)a®dca; = babaa.

15. N: 1)bd®b, 2)сd®bd, 3)db®l, 4)b®dcb; = abca.

16. N: 1)сdaa®c, 2)сa®с, 3)c®l, 4)cb®bca, 5)l ®c;=daaa.

17. N: 1)aс®сaa, 2)dс®сbd, 3)da®l, 4)a®dca; = abab.

18. N: 1)bdb, 2)dbbd, 3)cdda, 4)abb, 5)d; =accc.

19. N: 1)сdaa®c, 2)сa®b, 3)c®l, 4)b®bca, 5)l ®c; =daab.

20. N: 1)aс®сaa, 2)dс®сbd, 3)da®l, 4)a®dca; =abdb.

21. N: 1) dccad, 2) db, 3) bdcb; =adabc.

22. N: 1)aс®сaa, 2)dс®сbd, 3)da®l, 4)a®dca; =bdbac.

23. N: 1)bd®b, 2)сd®bd, 3)db®l, 4)b®dcb; =abdc.

24. N: 1)сdaa®c, 2)сa®с, 3)c®l, 4)cb®bca, 5)l ®c;=abdba.

25. N: 1)aс®сaa, 2)dс®сbd, 3)da®l, 4)a®dca; =aabdb.

26. N: 1)bdb, 2)dbbd, 3)cdda, 4)abb, 5)d; =dadb.

27. N: 1)сdaa®c, 2)сa®b, 3)c®l, 4)b®bca, 5)l ®c; =cad.

Задание 4. Доказать, что функция f(x) вычислима по Маркову.

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. ;

18. ;

19. ;

20. ;

21. ;

22. ;

23. ;

24. ;

25. ;

26. ;

27. .

Задание 5. Программа машины Тьюринга Т с внешним алфавитом А={а₀, 1} и алфавитом внутренних состояний Q={q₀, q₁, …, q₁₃} задана в виде таблицы:

	a0	1
q1	q2a0Л	q01
q2	q5a0	q3a0
q3	q4a0Л	q01
q4	q51	q41Л
q5	q0a0	q61Л
q6	q0a0	q7a0
q7	q8a0П	q01
q8	q91	q81П
q9	q0a0	q101Л
q10	q0a0	q11a0
q11	q12a0Л	q01
q12	q131	q121Л
q13	q0a0	q01

Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина каждое из следующих слов (в начальный момент времени машина находится в состоянии q₁ и обозревает крайнюю правую ячейку, в которой записан пустой символ а₀, в следующей слева ячейке уже записан символ 1).

1. а₀111а₀1а₀

2. а₀11а₀111а₀11а₀

3. а₀1а₀1а₀1111а₀

4. а₀111а₀1а₀

5. а₀1111а₀1а₀

6. а₀11а₀111а₀

7. а₀1111а₀11а₀

8. а₀1а₀111а₀

9. а₀11а₀111а₀11а₀

10. а₀1а₀11а₀

11. а₀11а₀1111а₀

12. а₀1а₀111а₀1а₀

13. а₀111а₀111а₀

14. а₀11111а₀11а₀

15. а₀111а₀11а₀1а₀а₀11а₀

16. 111а₀1111а₀

17. 1а₀а₀11111а₀

18. а₀111а₀1111a₀а₀

19. а₀111а₀а₀11а₀

20. а₀1111a₀а₀11а₀

21. a₀а₀11а₀111а₀

22. а₀111111а₀

23. а₀11a₀1а₀111а₀

24. а₀11а₀а₀1111а₀

25. а₀11a₀а₀11а₀

26. 111а₀а₀11а₀

27. 11а₀11111а₀

Задание 6. Построить машину Тьюринга Т, которая перерабатывает слово  в слово , не применяя пустых ячеек а₀ слева от данного слова. В состоянии q₁ обозревается крайняя левая ячейка слова.

1. =01001110, =111

2. =01101110, = 111

3. =1110111, =1000

4. =00000001, =1111

5. =0100100, =000

6. =1100010, =0000

7. =1000100, =1101

8. =011111010, =101

9. =0110100110, = 1110

10. =01100111, =1100

11. =00111101, =0001

12. =011100100, =010

13. =01100010, =00100

14. =101111100, =1000

15. =01001110, =110

16. =01101100, = 011

17. =11000011, =1011

18. =1111110001, =0011

19. =0100000, =101

20. =011100010, =0100

21. =1000000, =1001

22. =01001111000, =101

23. =110110, = 1110

24. =11111001, =1010

25. =10011110001, =1001

26. =0110100111, =100

27. =10001010, =0110

Задание 7. Доказать, что функция f(x) задания 4 вычислима по Тьюрингу.