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


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

230 Дж. Хартмйнис
Беря Пг > max(A/i, W2), мы получаем искомое бесконечное множество целых положительных чисел, для которых выполняются упомянутые неравенства.
Предыдущие результаты показали, что существует резкий скачок времени вычислений, когда мы переходим от регулярных вычислений к нерегулярным. Далее мы возвратимся к классификации сложности нерегулярных множеств по их времени вычислений на одноленточных машинах Тьюринга. Связанные с этим результаты для многоленточных машин Тьюринга можно найти в [2, 6].
ИЕРАРХИИ ВЫЧИСЛЕНИЙ С ОГРАНИЧЕННЫМ ВРЕМЕНЕМ
В этом разделе мы исследуем классификацию нерегулярных множеств по времени, которое требуется для их распознавания.
Для вычислимой функции Т(п) (R(n)) назовем класс Т(п) -распознаваемых (R(n) -распознаваемых) множеств последовательностей классом сложности и обозначим его через CT(CR)- Следующий результат показывает, что существует бесконечно много классов сложности.
Лемма 3. Если Т(п) — вычислимая функция, то существует рекурсивное множество последовательностей Л, не принадлежащее Ст.
Доказательство проводится обычным диагональным методом [2].
Далее мы покажем, что каждое вычисление можно ускорить в постоянное число раз, если допустить обычное сгущение входных цепочек, т. е. мы позволяем записывать несколько входных символов в одной ячейке ленты.
Теорема 5. Если А Т (п)- распознаваемо, то A (J1 /2Т (п)[)- распознаваемо.
Доказательство. Пусть входное слово уплотнено на два символа в каждой ячейке ленты и А распознаваемо машиной М за время Т(п). Тогда с помощью метода, аналогичного тому, который был использован в доказательстве теоремы 2 в [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 291 292 293 294 295 296 297 298 299 300 310 320 330 340 350 360 370 380 390 400 410 420 430


Математика