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


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

330 П. М. Льюис И, Р. Е. Стирнз, Дж. Хартманис
односторонними магазинными машинами. В частности, L? — пересечение следующих семи языков:
La = H?s (I ?sS?+Is)* (0 + 1 + и + z)*ss(\ + s)*,
/-> <- ч*
Lb = (bkSbk+is) ss(l + s)*,
Lc = (0 + 1 + s + и + z)*(0 + 1 + s) (u + zf ss
\qs(\ls\l~ls)*\*sss(\+s)\
ld = (0 + 1 + s + и + zY (u + z) ss (iW's)* l*sss (1 + s)*,
L, = (0-b 1 -f s-f « + e)*ss(l + -|)'sss(rs)r,
(s \r 1+-дг) sss (l*s)/" означает произвольную строку из еди-* I
ниц и символов s, за которыми следует sss, за которыми в свою очередь следует г групп l*s, при этом г равно числу единиц плюс половина числа символов s, содержащихся в этой произвольной строке,
}-\ + s + u + z)*sss\s(rsrs) Ts, Lg == (0 + 1 + s + и + z)* sss (rs!2ys)*. Как в доказательстве теоремы 1, La и L& дают начальную
часть LI до первого появления ss. Так как Ь%т последовательно пронумеровано, прямо перед ss будут находиться [log log 2m] символов «иг. Язык Lc тогда даст также_[^ log 2m] единиц сразу после ss. Языки Lc и Ld образуют L7 между ss и sss. В этой части число единиц равно
[log log 2m] + ([log log 2m] - 1) + ... + 2 + 1 =
= { {[log log 2m]2-[log log 2m]}.
Если к этому числу прибавить половину числа всех маркеров s> то получим точно
[log log 2m]2.
Le обеспечивает в точности это число, т. е. [log log2m]2 маркеров s после sss. Языки L/ и Lg дадут часть последовательности после sss. Осталось только показать, что все семь языков действительно разрешимы односторонней магазинной машиной. Это относительно просто.
Подобный метод дает все рациональные степени, превосходящие единицу, log log 2m и все рациональные дробные (не

 

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 331 332 333 334 335 336 337 338 339 340 350 360 370 380 390 400 410 420 430


Математика