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


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

240 Ф К. Хенни
обязанность машины вести «домашнее хозяйство» отрывает ее от основной работы по передаче информации о входном слове, и это значительно уменьшает вычислительную производительность машины. Способом борьбы с этим обстоятельством должно быть изменение метода, использованного при распознавании множества S. В случае модификации вычислительной схемы и значительного расширения внешнего алфавита становится возможным сконструировать машину с восемью состояниями, время вычисления которой приблизительно равно удвоенной данной нижней границе. Таким образом, в этом частном примере можно получить относительно высокую производительность передачи информации; первоначально данная нижняя граница будет относительно хорошей.
Нужно помнить, однако, что доводы, использованные для получения нижней границы времени вычисления, не учитывают того обстоятельства, какие встречающиеся следы может породить одноленточная машина Тьюринга. Так как модель машины Тьюринга сама налагает ограничения на следы, которые могут встречаться в данном вычислении, то нельзя ожидать, что аргументы, аналогичные аргументам этого раздела, приведут к хорошей нижней оценке для всех проблем распознавания1).
Проблема распознавания множества S интересна по нескольким причинам.
Во-первых, она иллюстрирует приложение понятия следа к проблеме определения минимального времени вычисления. Во-вторых, она дает специфический пример вычислительной проблемы, для которой можно получить достаточно близкие верхние и нижние границы времени. В-третьих, она дает некоторое представление о соотношении между следами, данной вычислительной схемой и «производительностью» этой схемы. Наконец, она дает информацию о соотношении скоростей одно- и двуленточ-ных машин, которая рассматривается ниже.
Рассмотрим проблему построения двуленточной машины Тьюринга с записью на ленте, которая распознает множество 5. Такая машина начинает свои вычисления, если входное слово записано на одной из ее лент, называемой входной лентой. Вторая лента, называемая внешней лентой, перед началом вычислений полностью пуста. Простой способ выполнения желаемого вычисления состоит из следующих трех шагов.
1) Результат, аналогичный изложенному выше, содержится в [6*] в более сильной форме: там построен пример такого множества, что распознавание принадлежности к нему для почти всех слов длины п требует времени порядка п2. Соотношению между числом состояний машины и временем ее работы на словах длины ^гс, о котором говорит автор, посвящена работа [5*]. Прим перев. и

 

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 241 242 243 244 245 246 247 248 249 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430


Математика