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


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

28Э П. Стрнад
Для />3 выполняется неравенство 2*(1 + 1) > 2i+2(t ' + 2) /5 и, поскольку функция U монотонно возрастает, имеет место неравенство
6-Mogs' откуда следует, что
.
6 • г • log s
ПОСКОЛЬКУ Ali+i > ft.
Для завершения доказательства теоремы 2 достаточно показать, что для бесконечно многих значений п имеет место неравенство U(n/5) > U(n)/25. Предположим, что это высказы вание ложно, т. е. что для почти всех п выполняется неравен ство U '(л/5) < U (п) /25 или 25-?/(л/5)<{/(я).
Тогда можно выбрать такое п0, что
U Ы > О, U
U (5*л0) >&* -U
Согласно предположению, U(n)^n2~B, поэтому
1
lim sup t/ (n)/n2~e< оо.
П->00
Таким образом, последовательность
U (5< •
(для f = 0, 1, 2, ...)
имеет lim sup, меньший, чем оо, но «->•«>
?7(5*.
• 58 —» оо,
что противоречит предположению.
Подведем теперь итог полученным результатам. Каждой монотонно возрастающей функции U(n), которая вычислима в реальное время и для которой имеет место соотношение п ^ U (/г) 2 1
слов Ац^ Л, такое, что
(1) Аи распознается машиной Тьюринга со входом Mv за время Т(п)= Ci'U(n) (согласно теореме 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 250 260 270 280 281 282 283 284 285 286 287 288 289 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430


Математика