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


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

250 Ф. К. Кении
сдвинуть каждую из ее лент на один квадрат в любом направлении и переменить внутреннее состояние. Общее число шагов, которые машина должна совершить, чтобы выдать выходные символы, связано с данной входной последовательностью и называется временем вычисления для этой входной последовательности. Если Т(п) —функция, такая, что время вычисления для каждой входной последовательности длины п меньше или равно Т(п), то говорят, что машина работает с временной границей Т (п). Входно-выходное преобразование, реализуемое машиной, будет называться «вычислимым с границей (или за время) Т(п)»\ множество последовательностей, распознаваемых машиной, будет называться «распознаваемым с границей (или за время) Т(п)».
Эта работа касается определения нижних границ времени вычисления некоторых входно-выходных преобразований и взаимосвязи между временем вычисления и размерностью лент машины Тьюринга. В разд. 2 рассматриваются одномерные ленты и описывается входно-выходное преобразование, для которого можно найти хорошую нижнюю границу времени вычисления. Метод, использованный при установлении этой границы, применяется в разд. 3, где показано, что увеличение размерности ленты от 1 до 2 иногда может значительно уменьшить время, требуемое на выполнение преобразования. Этот результат обобщается в разд. 4, где показано, что для многомерных лент «закон квадрата» Хартманиса — Стирнза [2, 3] не может быть значительно улучшен и что имеется существенная разница между размерностью и количеством лент машины Тьюринга.
2. ОДНОМЕРНЫЕ ЛЕНТЫ
В этом разделе исследуется вопрос о времени вычисления, необходимом для выполнения некоторого входно-выходного преобразования на машине Тьюринга с входом (on-line), которая использует одномерные ленты. Это преобразование может быть описано следующим образом. Машина Тьюринга снабжается сначала последовательностью входов, представляющих информацию, записанную на ленте (лентах) машины. Эта информация кодируется в форме блоков из нулей и единиц равной длины. После того как указанное число информационных блоков прочитано, машина переходит ко второй последовательности входов, также состоящей из блоков равной длины из нулей и единиц. Когда каждый из этих новых блоков прочитан, машина должна решить, был или нет такой же блок в первой части входной последовательности, а на выходе поставить 1 или 0 соответственно.

 

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 251 252 253 254 255 256 257 258 259 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430


Математика