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


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

420 М. Блюм
S*b
отношение Фт(г)(я) ^ Ю[ФТ(г)(я)]2, где 10 соответствует 10 лентам 10-ленточной машины.
Вычисление f(n) описывается в доказательстве теоремы 7. Далее следует повторение этап за этапом части доказательства, касающейся конструкции, вместе с утверждениями, заключенными в скобки, которые дают число шагов, необходимое для проведения каждого из этапов вычисления. Символ с всюду используется для обозначения константы. Чтобы вычислить f(n):
A. Вычислим Фг(я)=т и перейдем к шагу 0 = (0,0). Число шагов, необходимое, чтобы сделать это, составляет
+ с log n + cm log m]. Далее индуктивно
B. На шаге х = (p,q)
1. Определим, имеет ли место Фi(p}=q [pi^c + cq log q].
Предположим, что Фг- (/?)=#.
2. Выделим индексы sb ..., st всех невычеркнутых функций, принадлежащих множеству (ф0(р), ..., <рр(р)} [р2^с(р+ 1) (р + + 9) (log (p + q))].
3. Выберем наименьший индекс sh, такой, что Ф8 (p) /V
присоединим (sfe, p) к списку. Нам требуется определить следующие величины:
s (0 = df ~ число шагов, необходимое для того, чтобы напеча-
тать программу машины Zf; р
%s (i) [r(p) < ср2 log р]]
= 0
р
h где d^i(n) есть число шагов, необходимое для
того, чтобы смоделировать вычисление Zt на входе n [d(p) г (Р) + cd (Р)
C. Перейдем от шага п = (р, q) к шагу п + 1, если (p,q) Ф Ф (п, т) [у < с log р + с log ^ + с].
D. Если ни одна из функций Ф8(п) не вычеркнута на шаге (п,т), полагаем f(rc)=0. В противном случае Ф8(п) вычеркивается на шаге (п, га) и поэтому полагаем f (п) = 1— ф8(/г) [б^с].
Общее число шагов, требуемых для вычисления f(n) на 10-ленточной машине, составляет
т (О
/г+m п+т- q
а+ (Y + Pi)

 

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 421 422 423 424 425 426 427 428 429 430


Математика