Главная > Очерки по конструктивной математике
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
След.
Макеты страниц

Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO

9. Теоремы об итерации

Мы докажем, что произвольная рекурсивная нумерация рекурсивно перечислимых множеств может быть в определенном смысле сведена к универсальной нумерации.

Пусть рекурсивно перечислимое отношение между натуральными числами и словами в данном алфавите. Тогда можно найти общерекурсивную функцию такую, что равно композиции и универсального отношения

Эту теорему мы назовем теоремой об итерации для рекурсивно перечислимых множеств.

Доказательство. Рассмотрим алфавит и запишем схемы данного отношения, отмеченные знаком кроме того, схемы

Пусть -гёделевский номер этого рекурсивно перечислимого множества. Тогда общерекурсивная функция, удовлетворяющая условиям теоремы.

Действительно, если то тогда и только тогда, когда что как раз и означает, что равно композиции

Теорема об итерации для частично рекурсивных функций столь же проста.

Если дана частично рекурсивная функция то мы можем найти общерекурсивную функцию такую, что где универсальная функция.

По аналогии с доказательством предыдущей теоремы мы полагаем равным гёделевскому номеру сечения в точке

1
Оглавление
email@scask.ru