Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Сборник N.N. Проблемы математической логики Сложность алгоритмов и классы вычислимых функций
 
djvu / html
 

10 А. Гжегорчик
Например, следующие три функции являются функциями, нумерующими пары, с вышеописанными свойствами:
Q?, равная наибольшему целому числу и, такому, что г + 1 делится на 2й;
Rz= 2 .
Другими примерами функций, нумерующих пары, являются следующие функции /, /С, L l):
1
= z — w(w + 1), где и — наибольшее целое число, та-
кое, что -^
Lzt равная неотрицательному решению уравнения

^
= 2, т.е. z =
Имеем I(Kz, Lz) = z, K(I(x, y)) = xt L(I(x, y)) = y.
Функции, нумерующие пары, позволяют нам образовать функции троек, например
Т(х, у, г) = Р(х, Р(у, г)) или S(x, у, г) = 1(х, I (у, z))t
которые устанавливают соответствие между множеством троек чисел и самим множеством чисел. Обратными к Т функциями являются
TIU = Qu, T2u = QRu, T3u = RRu.
Аналогично все конечные наборы чисел могут быть представлены натуральными числами.
Буквы Р, Q, R и /, /С, L будут впоследствии обозначать тройки функций, нумерующих пары.
2. Универсальные функции. Все рассматриваемые в дальнейшего функции определены на множестве неотрицательных целых чисел и принимают целые значения. Мы будем употреблять названия «целое число» и «число» только в смысле «неотрицательное целое число». Прописными буквами $В> °У, $,, &п обозна-
1) Приведенные в оригинале функции /, /С, L не удовлетворяют свойствам функций, нумерующих пары. Поэтому мы их заменили функциями, связанными с обычным пересчетом пар натуральных чисел вдоль прямых х-\-у = ~ const. — Прим. перев,

 

1 10 11 12 13 14 15 16 17 18 19 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430


Математика