On two-tape real-time computation and queues

DOI10.1016/0022-0000(84)90001-1zbMath0552.68052OpenAlexW2024671403MaRDI QIDQ801685

Paul M. B. Vitányi

Publication date: 1984

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://ir.cwi.nl/pub/6570

zbMATH Keywords

queueTuring machineone-head tape unitstwo-head tape unit

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On heads versus tapes
• An information-theoretic approach to time bounds for on-line computation
• Real time computation
• k-Band-Simulation von k-Kopf-Turing-Maschinen. (k-tape simulation of k- head Turing machines)
• On-line simulation of k + 1 tapes by k tapes requires nonlinear time
• New Real-Time Simulations of Multihead Tape Units
• Algorithmic Information Theory
• Real-Time Simulation of Multihead Tape Units

This page was built for publication: On two-tape real-time computation and queues