Two-Tape Simulation of Multitape Turing Machines

DOI10.1145/321356.321362zbMath0148.24801OpenAlexW2004471951WikidataQ55923064 ScholiaQ55923064MaRDI QIDQ5526975

Publication date: 1966

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

Full work available at URL: https://doi.org/10.1145/321356.321362

zbMATH Keywords

mathematical logic

Related Items

The theory of languages ⋮ Turing Machines for Dummies ⋮ Generality's price: Inescapable deficiencies in machine-learned programs ⋮ Local Reductions ⋮ Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts ⋮ Time hierarchies for cryptographic function inversion with advice ⋮ A tight lower bound for on-line monotonic list labeling ⋮ On the simulation of many storage heads by one ⋮ Local reduction ⋮ The theory of languages ⋮ An application of the translational method ⋮ Tape versus queue and stacks: The lower bounds ⋮ Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time ⋮ Amplifying circuit lower bounds against polynomial time, with applications ⋮ Computational complexity of random access stored program machines ⋮ On restricted turing computability ⋮ Subrecursiveness: Machine-independent notions of computability in restricted time and storage ⋮ New time hierarchy results for deterministic TMS ⋮ On time hierarchies ⋮ Deterministic multitape automata computations ⋮ A hierarchy for nondeterministic time complexity ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ Effective guessing has unlikely consequences ⋮ Relativized depth ⋮ Hierarchy of complexity of computation of partial functions with values 0 and 1 ⋮ An improved simulation result for ink-bounded Turing machines ⋮ Complexity of algorithms and computations ⋮ An information-theoretic approach to time bounds for on-line computation ⋮ Milking the Aanderaa argument ⋮ The Undecidability of the Domino Problem ⋮ Modeling multitape Minsky and Turing machines by three-tape Minsky machines ⋮ On uniformity and circuit lower bounds ⋮ On quasilinear-time complexity theory ⋮ On the power of several queues ⋮ On the complexity of finite, pushdown, and stack automata ⋮ The network complexity and the Turing machine complexity of finite functions ⋮ Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines ⋮ Time-space tradeoffs for SAT on nonuniform machines ⋮ Relations between diagonalization, proof systems, and complexity gaps ⋮ A formalization of multi-tape Turing machines ⋮ Almost-everywhere complexity hierarchies for nondeterministic time ⋮ Time-restricted sequence generation ⋮ Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts ⋮ A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes ⋮ k-Band-Simulation von k-Kopf-Turing-Maschinen. (k-tape simulation of k- head Turing machines) ⋮ Zwei-Band Simulation von Turingmaschinen. (Two-tape simulation of Turing machines) ⋮ Domino-tiling games ⋮ Improved simulation of nondeterministic Turing machines ⋮ On non-determinacy in simple computing devices ⋮ Time-space tradeoffs for satisfiability ⋮ Linear-time simulation of multihead Turing machines ⋮ Writing stack acceptors ⋮ Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata ⋮ On two-way multihead automata ⋮ Time bounded random access machines ⋮ A linear time two tape merge ⋮ Data structures for distributed counting ⋮ Minimizing access pointers into trees and arrays ⋮ Complexity lower bounds for machine computing models ⋮ On average time hierarchies ⋮ Towards the Actual Relationship Between NP and Exponential Time ⋮ PAC-learning gains of Turing machines over circuits and neural networks