The reduction of tape reversals for off-line one-tape Turing machines
From MaRDI portal
Publication:2540551
DOI10.1016/S0022-0000(68)80028-5zbMath0199.31001OpenAlexW2094082874MaRDI QIDQ2540551
Publication date: 1968
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(68)80028-5
Related Items (12)
Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs ⋮ On reversal bounded alternating Turing machines ⋮ Complexity of algorithms and computations ⋮ On the complexity of 1-tape ATMs and off-line 1-tape ATMs running in constant reversals ⋮ The difference between one tape and two tapes: With respect to reversal complexity ⋮ Reversal-space trade-offs for simultaneous resource-bounded nondeterministic Turing machines ⋮ On the relationship between deterministic time and deterministic reversal ⋮ Reversal-bounded multipushdown machines ⋮ One way finite visit automata ⋮ Tape-reversal bounded Turing machine computations ⋮ A characterization of reversal-bounded multipushdown machine languages ⋮ Unnamed Item
This page was built for publication: The reduction of tape reversals for off-line one-tape Turing machines
