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


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

40 А. Гжегорчик
Предположим, что g и h — функции порядков / и k соответ-
ственно в классе W\ и что они удовлетворяют неравенству (6). Пусть k > /, тогда
8 (х) < fn+i (b, х), h (x) < fn+i (&, x).
Отсюда, поскольку fn+i — строго возрастающая функция, получаем
8(b(x)) l9 x).
Поэтому если f — функция порядка 6+1, полученная из функций g и h посредством одной из операций 1) или 2), то
f(x) х).
Таким образом, мы доказали теорему по индукции.
Теорема. 4.9. Функция /п+1 (х, х) растет быстрее, чем любая функция класса eft.
Доказательство. Для п^2 из теоремы 4.8 следует что если / — функция порядка k в классе Wn\ и x^k, то
f(x) Отсюда fn+i(xtx) растет быстрее любой функции класса T^i и в соответствии с теоремой 3.4 растет быстрее, чем любая
функция класса ^Т, так как исходные функции класса Отсюда функция 2л: растет быстрее любой функции и (х + I)2 растет быстрее, чем всякая функция f класса Таким образом, мы получили, что ^п с efft+1,
Теорема 4.10, Класс отношений %>п для п>1 является наименьшим классом, включающим исходные отношения
9 у, z^x = y R4(xt у, z) = x = y -*-2, R5(x, у, z) = * = /„( 1), R'Q(X, y) = RQ(x, у, у)

 

1 10 20 30 40 41 42 43 44 45 46 47 48 49 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


Математика