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


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

220 С. С. Раби, /7. К. Фишер
Теорема 2. Если U, Т е Fn и Т является существенной функцией для 8и ф Sy, то 8иот=?$Уот-
Доказательство. Пусть a^Sv — Su есть такая последовательность, что aft = 0, если неверно, что k — Т(п) для некоторого п. Тогда ат = ат (0}ат (1)аг (2) ... €= SK о г — 8Ц о г. Если
^~ — машина Тьюринга, которая ^-вычисляет а, то аг<Л) порож-
дается за 1/(Г(Аг)) операций машины 0~ . Поскольку T^Fn, то все выходы, кроме Г(0), Г(1), ..., Т(п)-то выходов ?Г, могут быть исключены за У(Г(«)) операций. В результате машина будет V (Т (п)) -вычислять ат. Если вдобавок сет порождается машиной ?Г' ', которая вычисляет ат точно за время U(T(n)), то, выдавая на выход 0 на U(k)-v\. операции, когда k не является значением Г, можно изменить &~' так, чтобы она порождала за U(k) операций, что противоречит условию теоремы. Справедливо также обращение теоремы 2.
Теорема 3. Из F, Т е /V, 5с/(Г(п)) ^ Sy (Г(Л)) следует, что Т является существенной функцией для 8и ^ Sv.
Доказательство. В доказательстве теоремы 1 р является последовательностью, которая делает Т существенной функцией.
Если R(T(n)) — существенная функция для 5и ф Sv, то R
существенна для Sv ф Sv, так как любая последовательность а,
с помощью которой устанавливается существенность R о Г, такую же роль играет в отношении R.
Теорема 4. ?7, Т е /v, lim - f- — = 0 влечет существенность
для ST ф Su для любого R e Fn.
Доказательство. Рассмотрим любое R^Fn. Тогда Su о я потому, что
.. Т (R (п) ) log Т (R (п) ) , Т (m) log Т (т)
11ГП - л /г> / ч ч - = ИГЛ - ггт — ; - — и. U(R(n)) m_>00 ?/(m)
По теореме 3 R существенна для ST ф Sv.
Fv -ИЕРАРХИЯ
Наряду с 5[/-иерархией обычно рассматривают тесно с ней связанную (напомним, что Т е Ри тогда и только тогда, когда ^[/-иерархию. Классы FU обладают интересными

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 221 222 223 224 225 226 227 228 229 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430


Математика