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


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

190 А. Розенберг
включающего почти все модели, которые могут быть использованы для изучения вычислений в реальное время. Для всякого п класс языков, определимых n-мерными итеративными сетями конечных автоматов (Коул [1]), не замкнут относительно итерации. Возвратимся снова к отношению Ek(modA) (определение 5).
Определение 10. Класс машин S№ есть класс полиномиально-ограниченных машин, если для каждой машины М из 9Й существуют константы сип, такие, что для /г^> 1 индекс отношения
ЕЙ (mod Л (М)) не превосходит ck .
Мы укажем несколько примеров классов полиномиально-ограниченных машин.
(1) Класс многоленточных машин Тьюринга, работающих в реальном масштабе времени.
(2) Для всякого п класс многоголовочных машин Тьюринга с я-мерными лентами, работающих в реальном масштабе времени.
(3) Для всякого п класс /г-мерных итеративных сетей конечных автоматов, работающих в реальном масштабе времени.
Внимательного рассмотрения доказательств разд. 4 доста* точно, чтобы доказать теорему 14.
Теорема 14. Пусть WI — класс полиномиально-ограниченных машин.
(a) Если класс языков L(3R), определимых Wl-машинами, включает класс языков, определимых работающими в реальное время PDS-автоматами, то L(2J?) не замкнут относительно сцепления даже с регулярным множеством относительно итерации и относительно отображения последовательностной машиной.
(b) Если класс языков, определимых Wt-машинами, включает класс языков, определимых 2-МР'В-машинами (что необходимо есть частный случай (а)), то L($fl) не замкнут относительно обращения и операций взятия производных и частных.
Можно заметить, что все языки, определимые с помощью любого класса машин из указанных выше, рекурсивны. Поэтому они не замкнуты относительно максимизации ввиду 4.6.
4.8. Положение R в лингвистической иерархии. В разд. 2 мы отмечали, что R— подкласс класса контекстных языков. Результаты разд. 3 и 4 показывают, что R не сравним с бесконтекстными (КС-) языками; так, существуют КС-языки (например, 2*Р из разд. 4.1), не являющиеся ЯРВ, и существуют языки, определимые в реальное время (такие, как [anb"cn: п^- 1}), не являющиеся КС-языками. В этом разделе мы представим пример де*

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 191 192 193 194 195 196 197 198 199 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430


Математика