On two-tape real-time computation and queues (Q801685)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On two-tape real-time computation and queues |
scientific article |
Statements
On two-tape real-time computation and queues (English)
0 references
1984
0 references
A Turing machine with two storage tapes cannot simulate a queue in both real-time and with at least one storage tape head always within o(n) squares from the start square. This fact may be useful for showing that a two-head tape unit is more powerful in real-time than two one-head tape units, as is commonly conjectured.
0 references
Turing machine
0 references
queue
0 references
two-head tape unit
0 references
one-head tape units
0 references
0 references
