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


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

30 А. Гжегорчик
Таким образом, из теоремы 3.1 вытекает, что класс 0.
Мы будем говорить, что функция f(x) растет быстрее, чем любая функция класса Я/, если для всякой функции g<^%? существует такое число nQ, что для каждого x^Z-nQ имеет место неравенство f(x)>g(x).
Функция f(xi,...,xn,...,Xh) называется неубывающей относительно п-го аргумента, если для всех х\, ..., хь. и у неравенство хп^у влечет
/ V-M, ...» Xnt ...» Xfc) ^55 / \Х\у ...» У) ...» %k)'
Функция, неубывающая относительно каждого своего аргумента, называется просто неубывающей. Функция называется возрастающей, если она удовлетворяет сформулированному выше условию с заменой неравенства <1 на строгое неравенство <.
Далее, будем говорить, что функция g мажорирует функцию f, если f(u) Теорема 3.3, Если классы $8 и *У индуктивно определимы посредством операции подстановки и, быть может, посредством операции ограниченной рекурсии и если класс %? включает в себя неубывающие функции, которые мажорируют (все) исходные функции класса °у, то для всякой функции f класса <%/ можно указать некоторую неубывающую функцию /7 из класса $6, которая мажорирует f и имеет столько же аргументов, сколько их имеет функция f.
Доказательство. Доказательство проводится по индукции относительно порядка функции f в классе ^/.
Для исходных функций это свойство предполагается (в условии теоремы) выполненным.
Если для любых функций g, h, j порядка ниже, чем /г, существуют такие неубывающие функции g\ h', /', что
(I) g(x> yXgf(xt у), (И) h(yXh'(y\ (III) /(*, u) и f — функция порядка п в классе ^, то, коль скоро f получена подстановкой функций f(xty) = g(x,h(y)), f мажорируется неубывающей функцией g'(x,h' (у)), поскольку из (I), (II) и из факта неубывания g' следует, что

 

1 10 20 30 31 32 33 34 35 36 37 38 39 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


Математика