Prove Queue Automaton is equivalent to Turing Machine

Problem Detail: 

A deterministic queue automaton (DQA) is like a PDA except the stack is replaced by a queue. A queue is a tape allowing symbols to be written (push) on the left-end and read (pull) on the right-end.

Actually I've proved that a 2-tape Turing Machine can simulate the DQA. Now I'm proving the DQA can simulate Turing Machine TM. Let the queue store all the input and the right-end symbol is the one being read. Suppose $a$ is the right-end symbol in the queue.

For the transition $\delta(q,a)=(r,b,L)$ in TM, it's easy to simulate. Just pull $a$ and push $b$. Now the right-end symbol would be the symbol on the left of $a$. It's like move the head in TM to the left.

My problem is I cannot find a way to simulate the transition $\delta(q,a)=(r,b,R)$. Since the symbol on the right of $a$ is actually the left-end symbol, how can I let this symbol move to the right-end? I spend several hours on this and I think answers on Internet are not very clear. Could anyone give me some hint?

Asked By : user3273554

Answered By : Vor

It is obvious that you can't handle all the right moves at the same time, so the trick is to use a special symbol to mark the head position ($\#$) and place it on the left of the symbol under the head:

queue: 0100100#1  equivalent to tape: __0100100[1]___ 

Now you pop the symbols from the right and re-push them on the left but with one symbol of delay (you buffer one symbol using the internal states). When you read a symbol $x$ and the internal buffer contains $z$ then you re-push $z$ on the queue:

queue: 0100101#1  pop:   buf:* (initially the buffer contains the * marker, see below)      queue:  0100101#  pop:1  buf:*  queue:  *0100101  pop:#  buf:1   

When you pop $\#$ then you know that the symbol $x$ in the (internal) buffer is the symbol under the head, and you can apply the corresponding transition:

** if the transition says to write symbol $y$ and goto to $Right$ then you push $\#$ and the $y$ on the left of the queue.

 queue:    *0100101   pop:#  buf:1  apply transition Write 0 go Right  queue:  0#*0100101   pop:   buf:    queue:   0#*010010   pop:1  buf:  queue:    0#*01001   pop:0  buf:1  queue:    10#*0100   pop:1  buf:0  ... 

Then you continue the pop-push operations until you find again the $\#$.

** if the transition says to write symbol $y$ and goto to $Left$ then you can simply push $y$ on the left of the queue and keep the $\#$ in the internal buffer, read the next symbol and apply another transition until you find a Right move again:

queue:    *0100101   pop:#  buf:1  apply transition Write 0 go Left queue:    0*010010   pop:1  buf:#  apply transition Write 1 go Left queue:    10*01001   pop:0  buf:#  apply transition Write 1 go Right queue:  1#10*01001   pop:   buf:   ... 

The special symbol $*$ marks the begin/end of the tape and you can use it to handle the tape expansion on both directions. Now, you should be able to discover how by yourself. And if you want to be rigorous, you should also consider the special initial case in which the queue doesn't contain the head symbol #.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21460