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


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

430 М. Блюм
5) Для всех х из того, что <р,-(я) определена, следует, что h(x, Фг(х)) <Фg(j)(x) (т. е. MI делает значительно меньше шагов чем Mg(j)).
Доказательство. Выберем любое число L Мы ищем такое /, для которого имеют место п. 3—5. Это / определяется следующим образом: определим частично рекурсивную функцию г(п,х,у), равномерную относительно f,h,g,i (равенство 1). По теореме рекурсии получаем рекурсивную функцию q, такую, что Фд(п)(л;) = r(n,x, q(n)) (равенство 2). Эта функция q равномерна относительно f, h, g, i. Наконец, мы покажем, как выбрать эффективно п так, чтобы / = q(n) удовлетворяло п. 3—5.
Равенство 1. г(п,х,у)=п, если f\i ^\g(y)\ (т. е. если п. 4 не выполнен при (/=/), и г(п, х, у) =фг-(л:), если
(1) f(i)<\g(y) (п. 4 имеет место для y = j),
(2) фг-(л:) определена,
(3) h(x,($i(x)) <Ф8(У)(х) (п. 5 выполняется при y = j). В остальных случаях г(п,х,у) не определена.
Функция г вычислима. Теорема рекурсии1) дает нам рекурсивную функцию q, равномерную относительно /, h, g, i, такую, что
ЧУю (x) = r(n, x,
Исключая г, мы получаем
Равенство 2. фд(П)(х)=п, если f\ и ф если
(1) №<\8Я(п)\,
(2) фг(я) определена,
(3) }1(х,Фг(х))<Фёд(п)(х).
В остальных случаях qq(n)(x) не определена.
Как выбрать п> Заметим сначала, что f \i\^\gq(n) \ означает, что существует машина, которая вычисляет константную функцию ygq(n) (х) = фд(п) (х) = п и объем которой меньше некоторого фиксированного целого числа f\i\. Это невозможно для всех п, поэтому существует такое п, что \f(i) <\gq(n) . Чтобы найти это значение п, мы просто проверяем g(0), q(l), q(2), ... до тех пор, пока не найдем п, для которого \f(i) < <\gq(n) - При таком способе выбора п положим / = q(n). Таким образом п. 4 удовлетворяется. Отсюда следует
') Расширенная теорема рекурсии утверждает, что для каждой частично рекурсивной функции г(х\, ..., хт, у\, ..., уп, г) существует рекурсивная функция q, равномерная относительно г и такая, что
• • •» Ут) \Уit • • •» Уп) 1ШГ (*ь • •.» xmt yi, ..., уп, Я

 

1 10 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 431


Математика