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


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

210 Ф. /(. Хенна, Р. Е. Стирнз
тривается как входная лента. Машина начинает работать в фиксированном начальном состоянии, а на входной ленте записано некоторое слово. Это слово ограничено с обеих сторон пустыми квадратами, и его самый левый символ находится под считывающей головкой. При обработке каждого входного слова машина в конце концов попадает в состояние (заключительное), с которым связан выход. Говорят, что входное слово допускается в том и только в том случае, когда этот выход есть 1. Множество R конечных слов Т(п) -распознаваемо (машиной с записью на ленте) тогда и только тогда, когда существует машина Тьюринга с записью на ленте, которая обрабатывает любое входное слово длины п за Т(п) операций и допускает в точности слова из R.
Теорема 6. Если множество R распознается k-ленточной машиной Тьюринга с записью на ленте за время Т(п), то оно может распознаваться двуленточной машиной с записью на ленте за время T(n)\ogT(n).
Доказательство. Опять доказательство по существу не отличается от доказательства теоремы 2.
Теорема 7. Если U(n)—вычислимая в реальное время функция, то существует множество конечных последовательностей R, которое U (п)-распознаваемо машиной с записью на ленте, но не Т (п)-распознаваемо, где функция Т(п) такова, что
f Т (п) log Т (п) _п 1ШЭ и(п) ~и-
Доказательство. Построим машину D с записью на ленте, которая имеет входной алфавит {0, 1} и распознает множество R за время U(n). Эта машина интерпретирует каждое входное слово как двоичное представление целого числа. Основной частью работы D является моделирование вычисления, производимого 1-й двуленточной машиной Тьюринга с записью на ленте при обработке данного, входного слова. Две ленты D выделяются для того, чтобы использовать их для записи ситуаций на лентах моделируемых машин Мг-.
Перед началом работы D измеряет длину входного слова и отмечает ее на вспомогательной ленте. Затем это слово, подходящим образом закодированное, копируется на соответствующую ленту. Далее происходит подготовка к имитации машины Мг-. И наконец начинается имитация вычисления, выполняемого MI при обработке данного входного слова.
Машина D порождает характеристическую последовательность функции U(n) и сравнивает число единиц в этой после-

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 211 212 213 214 215 216 217 218 219 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430


Математика