On heads versus tapes

DOI10.1016/0304-3975(83)90063-4zbMath0536.68050OpenAlexW2029121016MaRDI QIDQ792093

Wolfgang J. Paul

Publication date: 1984

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(83)90063-4

zbMATH Keywords

real-time computationreal-time simulationd-dimensional Turing machinedescriptional complexity of rectangular figures

Mathematics Subject Classification ID

Related Items (6)

On the structure of one-tape nondeterministic Turing machine time hierarchy ⋮ \(k\) versus \(k+1\) index registers and modifiable versus non-modifiable programs ⋮ Linear-time simulation of multihead Turing machines ⋮ On computation with pulses ⋮ On two-tape real-time computation and queues ⋮ An \(n^{1.618}\) lower bound on the time to simulate one queue or two pushdown stores by one tape

Cites Work

• Unnamed Item
• k-Band-Simulation von k-Kopf-Turing-Maschinen. (k-tape simulation of k- head Turing machines)
• New Real-Time Simulations of Multihead Tape Units
• Real-Time Simulation of Multihead Tape Units

This page was built for publication: On heads versus tapes