2015-06-28
432
I. Выяснить применима ли машина Тьюринга, задаваемой программой:
q 
0 à q 
0R
q 1 à q 1R
q 0 à q 
0 R
q 1 à q 1L
q 0 à q 
0
q 1à q 1R
К следующим словам:
1) q 1 
0 
1
2) q 1 0 1 
3) q 1 0 1
4) q 101
5) q 1 0 1
6) q 10 1
7) q 1 01
8) q 1 0 1
9) q 1 0 1
10)q 1 0 1
II. Построить машину Тьюринга, вычисляющую следующую функцию.
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с.
