Лабораторная работа 9

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

q0 q0R;

q1 q1R;

q0 q0 R;

q1 q1L;

q0 q0;

q1 q1R.

К следующим словам:

1. q101;

2. q101;

3. q101;

4. q101;

5. q101;

6. q101;

7. q101;

8. q101;

9. q101;

10)q101.

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

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);

28);

29)

30)

Вопросы для самоконтроля

1 Что Вы понимаете под машиной Тьюринга?

2 Из каких частей состоит машина Тьюринга?

3 Дайте определение машинного слова.

4 Какая функция называется числовой?

5 Какая функция называется частично числовой?

6 Дайте определение функции, вычислимой по Тьюрингу.

7 Какие функции называются простейшими?

8 Дайте определение операций суперпозиции, примитивной рекурсии и минимизации.

9 Сформулируйте тезис Черча.

10 Сформулируйте тезис Тьюринга.

11 Какая связь между функциями, вычислимых по Тьюрингу и частично рекурсивными функциями?

Литература

1 Яблонский, С. В. Введение в дискретную математику [Текст] : учебное пособие для вузов по специальности «Прикладная математика» / С. В. Яблонский. – М. : Наука, 1979. – 272 с.

83