Computational Complexity of One-Tape Turing Machine Computations

DOI10.1145/321450.321464zbMath0162.31703OpenAlexW2087008115MaRDI QIDQ5545959

Juris Hartmanis

Publication date: 1968

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1813/5880

zbMATH Keywords

recursion theory, constructive mathematics

Related Items (27)

A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems ⋮ On the bit complexity of distributed computations in a ring with a leader ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Computational complexity of random access stored program machines ⋮ Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers* ⋮ On restricted turing computability ⋮ Reversible Limited Automata ⋮ New time hierarchy results for deterministic TMS ⋮ Weight-reducing Turing machines ⋮ Deterministic multitape automata computations ⋮ Complexity of algorithms and computations ⋮ Descriptional complexity of limited automata ⋮ An NP-complete language accepted in linear time by a one-tape Turing machine ⋮ Verifying time complexity of Turing machines ⋮ Iterated uniform finite-state transducers on unary languages ⋮ Verifying whether one-tape Turing machines run in linear time ⋮ Complexity of Nondeterministic Multitape Computations Based on Crossing Sequences ⋮ Relations between diagonalization, proof systems, and complexity gaps ⋮ Descriptional complexity of iterated uniform finite-state transducers ⋮ A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes ⋮ On Simulation Cost of Unary Limited Automata ⋮ A note on context free languages, complexity classes, and diagonalization ⋮ Deterministic Turing machines in the range between real-time and linear-time. ⋮ Converting nondeterministic two-way automata into small deterministic linear-time machines ⋮ Deterministic and nondeterministic iterated uniform finite-state transducers: computational and descriptional power ⋮ Fast parallel language recognition by cellular automata

This page was built for publication: Computational Complexity of One-Tape Turing Machine Computations