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


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

СЧЕТЧИКОВЫЕ МАШИНЫ И СЧЕТЧИКОВЫЕ ЯЗЫКИ1)
П. Фишер, А. Мейер, А. Розенберг
ВВЕДЕНИЕ
В последние годы возрос интерес к исследованию сложности вычислений на машинах Тьюринга. Параллельно с работой по изучению машин Тьюринга с ограничениями на время и пространство2) мы изучаем машины с подобными ограничениями, у которых вместо лент используются счетчики. Счетчиковые машины (СМ) вначале кажутся слабее, чем машины Тьюринга (ТМ), но, как показал Минский [8], возможности СМ без ограничений столь же велики, как у ТМ. СМ с ограничениями значительно удобнее для рассмотрения, чем соответствующие ТМ, поэтому многие вопросы, остающиеся открытыми для ТМ с ограничениями, решаются в этой работе для СМ с ограничениями.
Мы будем в основном рассматривать машины — распознаватели языков. Многие свойства ТМ-распознавателей переносятся на СМ, например свойства, связанные с замкнутостью классов языков, распознаваемых в реальное время. С другой стороны, можно продемонстрировать ряд существенных различий между ТМ и СМ; соответствующие свойства ТМ и СМ будут сопоставляться на протяжении всей работы.
Разд. 1 содержит формальное определение СМ-распознава-теля. Устанавливается связь между этим определением и его возможными вариантами. В разд. 2 мы исследуем несколько конкретных проблем распознавания, чтобы глубже раскрыть вычислительные возможности СМ. Разд. 3 связан с ограничениями на пространство для СМ. Мы устанавливаем непосредственную связь между временными и пространственными ограничениями на СМ и показываем изоморфизм возникающих в результате пространственных ограничений иерархий у ТМ и СМ. Разд. 4 содержит замечания о времени, которое требуется для моделирования одного вида машины на другом. Наконец, в разд. 5 мы исследуем свойства классов языков, которые определимы СМ
') Fischer Р. С., М е у е г A. R., Rosenberg A. L, Counter machines and counter languages, Mathematical Systems Theory, 2, № 3 (1968), 265—283.
2) На длину ленты. — Прим. ред.

 

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 381 382 383 384 385 386 387 388 389 390 400 410 420 430


Математика