On two-tape real-time computation and queues (Q801685)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3880120
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On two-tape real-time computation and queues |
scientific article; zbMATH DE number 3880120 |
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
0.8406689763069153
0 references
0.8343716263771057
0 references
0.8300127983093262
0 references
0.8034493923187256
0 references
