On the power of several queues

AbstractWe present almost matching upper and lower time bounds for the simulation of Turing machines with many queues, tapes, or stacks on Turing machines with few queues. In particular, the power of two queues in comparison with other storage types is clarified. We show that t(n)-time-bounded multistorage Turing machines can be simulated in time O(t(n)1 + 1/k) on k-queue machines. Every online simulation of k + 1 queues (or of two tapes) on k queues requires time Ω(t(n)1 + 1/k/polylog t(n)). The lower bounds are based on Kolmogorov complexity