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


Книга: Главная » Петер Р.N. Рекурсивные функции
 
djvu / html
 

240 _ •_ _ РЕКУРСИВНЫЕ ФУНКЦИИ _
то функция v (т) = v' (т) + т также обще-рекурсивна и удовле1-творяет условию v(/re)>/re; далее, так как v (т) > v' (т), при п, п* > v (т) справедливо неравенство
В качестве я* можно взять и число v(m). Поэтому для n>v(rri) выполняется неравенство
\а а |_ V* (k'n) |ая~а»(я)1 — 2j~2* --
<
2* - -25r* ft-0 *-o
Последнее неравенство только усилится, если в уменьшаемом произведем суммирование лишь до v (т):
\ 2m * ft-o
Так как ф(/ге, п) — монотонно неубывающая функция от п и п > v (т), то все слагаемые неотрицательны. Так как v (т) > т, то среди них встречается слагаемое
ф(от, п)— ф(от, v (от)) 2/п
Числитель этого слагаемого неотрицателен, поэтому сумма может только в том случае быть меньше 1/2"1, если этот числитель равен 0, т.е. если
Это равенство должно выполняться для всех ?i>v(/7i).
Итак, установлено, что если последовательность ап эффективно сходится, то для произвольного наперед заданного т существует такое п [а именно, « = v (т)], начиная с которого значения ф(/ге, п) остаются постоянными для всех п. Следовательно, наименьшее п, для которого ф (т, «)= 1, можно искать среди чисел до v(/re). С другой стороны, согласно определению функции ф, сформулированному в предыдущем пункте, значение ф (/те, п) при произвольном т впервые равно 1 при таком п, при котором значение р(т, п) впервые равно 0. Поэтому наименьшее х, для которого р(т, x)—Q, можно искать среди чисел до v(/re):
ftr IP (те> *) = °1 = V-* Iх *? v (т)& Р (т> *) = °1 •
Функция, стоящая в правой части [обозначим ее через <р(т)], является обще-рекурсивной функцией от /тг. Действительно, мы

 

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 241 242 243 244 245 246 247 248 249 250 260


Математика