Two-Tape Simulation of Multitape Turing Machines

Cited in

(69)

Subrecursiveness: Machine-independent notions of computability in restricted time and storage
Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts
Linear-time simulation of multihead Turing machines
A tight lower bound for on-line monotonic list labeling
Lower bounds for Levin-Kolmogorov complexity
Deterministic multitape automata computations
Minimizing access pointers into trees and arrays
Relations between diagonalization, proof systems, and complexity gaps
New time hierarchy results for deterministic TMS
Milking the Aanderaa argument
PAC-learning gains of Turing machines over circuits and neural networks
Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time
An information-theoretic approach to time bounds for on-line computation
Characterizations of pushdown machines in terms of time-bounded computers
Modeling multitape Minsky and Turing machines by three-tape Minsky machines
Time hierarchies for cryptographic function inversion with advice
Relativized depth
Writing stack acceptors
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
On the complexity of finite, pushdown, and stack automata
An application of the translational method
On restricted turing computability
The theory of languages
Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts
Complexity barriers as independence
A formalization of multi-tape Turing machines
Local reduction
Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
The theory of languages
On the power of several queues
Structure in average case complexity
On two-way multihead automata
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
Effective guessing has unlikely consequences
Differentially oblivious Turing machines
Time bounded random access machines
Tape versus queue and stacks: The lower bounds
On average time hierarchies
Computational complexity of random access stored program machines
Towards the Actual Relationship Between NP and Exponential Time
A hierarchy for nondeterministic time complexity
Data structures for distributed counting
A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
Improved simulation of nondeterministic Turing machines
The network complexity and the Turing machine complexity of finite functions
On time hierarchies
On non-determinacy in simple computing devices
On uniformity and circuit lower bounds
Amplifying circuit lower bounds against polynomial time, with applications
Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
Good things come to those who wait. Dishonest-majority coin-flipping requires delay functions
Generality's price: Inescapable deficiencies in machine-learned programs
Almost-everywhere complexity hierarchies for nondeterministic time
On quasilinear-time complexity theory
Complexity lower bounds for machine computing models
Time-restricted sequence generation
Oblivious complexity classes revisited: lower bounds and hierarchies
Turing machines for dummies. Why representations do matter
Time-space tradeoffs for SAT on nonuniform machines
On the simulation of many storage heads by one
A linear time two tape merge
The undecidability of the domino problem
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
Time-space tradeoffs for satisfiability
Local reductions

This page was built for publication: Two-Tape Simulation of Multitape Turing Machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5526975)