On heads versus tapes

DOI10.1016/0304-3975(83)90063-4zbMATH Open0536.68050OpenAlexW2029121016MaRDI QIDQ792093FDOQ792093

Authors: 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

Recommendations

• Two heads are better than two tapes
• Two heads are better than two tapes
• On long runs of heads and tails
• On long runs of heads and tails. II
• Head-Media Interaction in Magnetic Recording
• Head-media interaction in magnetic recording

zbMATH Keywords

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Real-Time Simulation of Multihead Tape Units
• Title not available (Why is that?)
• k-Band-Simulation von k-Kopf-Turing-Maschinen. (k-tape simulation of k- head Turing machines)
• New Real-Time Simulations of Multihead Tape Units

Cited In (8)

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

This page was built for publication: On heads versus tapes

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