Hierarchies of memory limited computations
- 1 January 1965
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 179-190
- https://doi.org/10.1109/focs.1965.11
Abstract
This paper investigates the computational complexity of binary sequences as measured by the rapidity of their generation by multitape Turing machines. A "translational" method which escapes some of the limitations of earlier approaches leads to a refinement of the established hierarchy. The previous complexity classes are shown to possess certain translational properties. An related hierarchy of complexity classes of monotonic functions is examinedKeywords
This publication has 6 references indexed in Scilit:
- On the Computational Complexity of AlgorithmsTransactions of the American Mathematical Society, 1965
- Memory bounds for recognition of context-free and context-sensitive languagesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1965
- Computational complexity of recursive sequncesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1964
- Classes of Predictably Computable FunctionsTransactions of the American Mathematical Society, 1963
- Real-Time Computation and Recursive Functions Not Real-Time ComputableIEEE Transactions on Electronic Computers, 1962
- On Computable Numbers, with an Application to the EntscheidungsproblemProceedings of the London Mathematical Society, 1937