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


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

270 Ф. К. Хенни
Б действительности уменьшение размерности ленты квадрата времени вычисления. Этот вопрос очень уместен, так как он показывает, что уменьшение числа лент у машины Тьюринга не влечет существенного увеличения времени вычисления в предположении, что ленты одномерны и число лент не меньше двух [5].
Еще не ясно, необходим ли квадрат. Результаты разд. 3 и 4, А показывают, что существенное увеличение времени вычисления необходимо по крайней мере для некоторых проблем, когда число измерений уменьшается. В частности, если число измерений уменьшается от т до /, то время вычисления может вырасти в степень (2m — j)/m. Таким образом, если число измерений сильно уменьшается, то время вычисления должно увеличиться в степени, близкой к 2.
Итак, имеем, что добавление каждого нового измерения дает иногда уменьшение времени вычисления, по крайней мере для некоторых проблем. Для обсуждаемых здесь примеров этот выигрыш уменьшается с каждым новым измерением, но не ясно, всегда ли это будет иметь место. Понятно то, что размерность ленты и количество лент влияют на время вычисления по-разному. Если увеличение числа измерений может существенно уменьшить порядок роста времени вычисления, то увеличение числа (одномерных) лент свыше двух не меняет существенно порядка роста времени вычисления.
ЛИТЕРАТУРА
1. Hennie F С, One-tape, off-line Turing machine computations, Information and Control, 8 (1965), 553—578. (См. стр. 223—248 настоящего сборника.)
2. Hartmanis J., Stearns R. E., On the computational complexity of algorithms, Trans. Amer. Math. Soc., 117 (1965), 285—306 (Русский перевод: Кибернетический сборник (новая серия), вып. 4, «Мир», 1967.)
3. Н а г t m a n i s J., Stearns R. E., Computational complexity of recursive sequences, 1964 Proc. of the Fifth annual Symp. on Switching Circuit Theory and Logical Design, p. 82.
4. Y a m a d a H., Real-time computation and recursive functions not real-time computable, IRE Trans, on Electronic Computers, EC-11 (1962), 753—760 (См. стр. 139—155 настоящего сборника.)
5. Н е n n i e F., Stearns R. E., Two-tape simulation of multitape Turing machines, JACM, 13, № 4 (1966), 535—546. (См. настоящий сборник стр. 194—212.)

 

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 271 272 273 274 275 276 277 278 279 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430


Математика