Two heads are better than two tapes
Authors:
Open Access
- 1 March 1997
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 44 (2) , 237-256
Abstract
We show that a Turing machine with two single-head one-dimensional tapes cannot recognize the set.Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- An Introduction to Kolmogorov Complexity and Its Applications1993
- The Power of the QueueSIAM Journal on Computing, 1992
- Tape versus queue and stacks: The lower boundsInformation and Computation, 1988
- Combinatorial lower bound arguments for deterministic and nondeterministic Turing machinesTransactions of the American Mathematical Society, 1985
- Two nonlinear lower bounds for on-line computationsInformation and Control, 1984
- New Real-Time Simulations of Multihead Tape UnitsJournal of the ACM, 1981
- Saving tapes in the simulation of multihead turing machinesACM SIGACT News, 1974
- Real-Time Simulation of Multihead Tape UnitsJournal of the ACM, 1972
- On-Line Turing Machine ComputationsIEEE Transactions on Electronic Computers, 1966
- On the computational complexity of algorithmsTransactions of the American Mathematical Society, 1965