Tape bounds for time-bounded Turing machines

DOI10.1016/S0022-0000(72)80017-5zbMath0236.02031OpenAlexW1980572240MaRDI QIDQ2552124

Michael S. Paterson

Publication date: 1972

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(72)80017-5

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Turing machines and related notions (03D10)

Related Items (19)

On the structure of one-tape nondeterministic Turing machine time hierarchy ⋮ Complexity and Polynomially Solvable Special Cases of QUBO ⋮ Relating the power of cellular arrays to their closure properties ⋮ Parallel computation with threshold functions ⋮ On time versus space III ⋮ On alternation ⋮ On some open problems concerning the complexity of cellular arrays ⋮ A space bound for one-tape multidimensional Turing machines ⋮ On time versus space. II ⋮ Complexity of algorithms and computations ⋮ Time complexity of multidimensional Turing machines ⋮ On minimal-node-cost planar embeddings ⋮ Space bounds for a game on graphs ⋮ Log space machines with multiple oracle tapes ⋮ Complexity of Nondeterministic Multitape Computations Based on Crossing Sequences ⋮ Space-bounded simulation of multitape turing machines ⋮ Complexity lower bounds for machine computing models ⋮ Unnamed Item ⋮ Speedups of deterministic machines by synchronous parallel machines

Cites Work

• Relationships between nondeterministic and deterministic tape complexities
• Relations Between Time and Tape Complexities
• Unnamed Item

This page was built for publication: Tape bounds for time-bounded Turing machines