Linear speed-up does not hold on Turing machines with tree storages

DOI10.1016/0020-0190(93)90078-NMaRDI QIDQ688445zbMATH OpenFDO

Authors Martin Hühne

Publication date 20 December 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(93)90078-N

zbMATH Keywords

computational complexityKolmogorov complexitylower boundsonline simulationspeed-uptree storageTuring machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Review text

One of the basic results in computational complexity is the linear speed- up theorem by \textit{J. Hartmanis} and \textit{R. E. Stearns} [Trans. AMS 117, 285-306 (1965; Zbl 0131.154)]: On Turing machines accessing tapes as storage constant factors in the computation time are not significant, since any computation can be increased in speed by any constant factor. In this paper Turing machines accessing storage devices with a tree-like structure are studied. It is shown that on tree storage machines constant factors are significant. For any \(k\), power of two, there is a modification of the Storage-Retrieval Problem which can be solved in time \(kn\) on a machine with two binary tree storages. On the other hand, any binary tree storage machine (even if it is equipped with more storages) requires time \(kn-O(n/ \log n)\) to solve this problem.

Recommendations

• scientific article; zbMATH DE number 6292628
• A speed-up theorem without tape compression
• Fast Simulation of Turing Machines by Random Access Machines
• scientific article; zbMATH DE number 4213433
• The hedge: an efficient storage device for Turing machines with one head

Cites work

• A fast implementation of a multidimensional storage into a tree storage
• Boolean Memories
• Deterministic simulation of a single tape turing machine by a random access machine in sub-linear time
• scientific article; zbMATH DE number 4213433 (Why is no real title available?)
• scientific article; zbMATH DE number 3936519 (Why is no real title available?)
• scientific article; zbMATH DE number 44418 (Why is no real title available?)
• scientific article; zbMATH DE number 1142293 (Why is no real title available?)
• Minimizing access pointers into trees and arrays
• On the Computational Complexity of Algorithms
• On the Minimum Computation Time of Functions
• On time versus space. II
• Optimal Dynamic Embedding of Trees into Arrays
• Optimal On-Line Simulations of Tree Machines by Random Access Machines
• Relations Among Complexity Measures

Cited in

(1)

• Space measures for storage modification machines

This page was built for publication: Linear speed-up does not hold on Turing machines with tree storages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q688445)