Question

"A queue automaton is like a push-down automaton except that the stack is replaced by a queue. A queue is a tape allowing symbols to be written only on the left-hand end and read only at the right-hand end. Each write operation (we’ll call it a push) adds a symbol to the left-hand end of the queue and each read operation (we’ll call it a pull) reads and removes a symbol at the right-hand end. As with a PDA, the input is placed on a separate read-only input tape, and the head on the input tape can move only from left to right. The input tape contains a cell with a blank symbol following the input, so that the end of the input can be detected. A queue automaton accepts its input by entering a special accept state at any time. Show that a language can be recognized by a deterministic queue automaton iff the language is Turing-recognizable."

Answer 1

It is possible in this example to show that a language can be recognized by a deterministic queue automaton if the language is Turing-recognizable.

For computation, we first need to transfer the input string on queue. We do so by using right moves and pushing each read symbol. Then, we simulate the right move of TM with pull of the rightmost elements of the queue and pushing the new symbol according to transition function back to queue. On the other hand, the left reset of TM is simulated using pushing until we reach special symbol which denotes the left-hand end of tape. We push and pull until we are at the right position. Therefore, we can intuitively simulate left-reset Turing machines.