It can be proven that class of languages accepted by queue automata is equal to class of languages accepted by Turing machines. It was mentioned somewhere that the language $$L = \{x\#x^R \mid x\in\{0,1\}^* \} $$ can not be accepted by a queue automaton. But the language is accepted by a TM. Can somebody explain this apparent contradiction?
$\begingroup$
$\endgroup$
7
-
1$\begingroup$ Clearly, one statement is false. Have you looked at proofs for either? Are the notions of "queue automaton" exactly the same for both statements? $\endgroup$– RaphaelCommented Jan 1, 2015 at 12:40
-
$\begingroup$ Unfortunately it is a test with four choices which it says which of the choices is not accepted by a queue automaton with unlimited capacity. An it says the correct answer is this one!?! $\endgroup$– n.PerceptionCommented Jan 1, 2015 at 12:50
-
$\begingroup$ Other Languages in the test: $L = \{x\#x \mid x\in\{0,1\}^* \}$ $\endgroup$– n.PerceptionCommented Jan 1, 2015 at 12:50
-
2$\begingroup$ Wikipedia also thinks that queue automata are Turing-complete. The languages that you mention cannot be accepted by finite state automata (DFAs/NFAs). Multiple-choice questions are not a great learning resource. $\endgroup$– Yuval FilmusCommented Jan 1, 2015 at 14:05
-
$\begingroup$ Yea. Actually i'm not using multiple-choice questions for learning. I faced to one of them and just got interested to know why this language can not be accepted by queue automata... $\endgroup$– n.PerceptionCommented Jan 1, 2015 at 18:09
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
If a queue automaton is Turing-Complete, then it can compute (decide) any function (language) that a Turing machine can. And we know that TM can decide both $L = \{x\#x^R \mid x\in\{0,1\}^* \}$ and $L = \{x\#x \mid x\in\{0,1\}^* \}$, thus both can be decided by a queue-automaton.
"How?" you ask? For this you need to understand how a queue-automaton works. It starts with the input already in the queue (where the end of the input is marked by a special character $\$$), and then at every move it reads the letter at the head of the queue and can insert one or more characters to the end of the queue.
Let $M$ be a TM. The way to simulate $M$ over the queue automaton is to keep reading content out of the queue and then putting it back into the end of the queue. This allows us to make multiple passes over the "tape" of the TM. For instance, assume the queue holds "abc$". A "Cycle" (a pass on the queue) will look like (plotting the queue content):
abc$ -> bc$a -> c$ab -> $abc -> abc$
and we are back to square one, allowing the machine now to take another pass on the input.
It is then trivial to simulate the TM moves as long the head moves to the right, or stays in place: we can denote the heads place by a special symbol ($\to$) that points on where the TM head looks at. E.g., at the very first move we do:
abc& -> bc$→a -> c&→ab -> ... -> →abc$
Then moving the head to the right is elementary:
→abc& -> abc$ -> bc&a→ -> ... -> a→bc$
It is a bit more tricky to simulate a move of the TM head to the left, because seemingly, we need to put the head even before we see the next letter that causes the move back.
The trick here is to use the current state in order to "keep one letter in the memory". So when we see a letter, we don't immediately put it back to the queue, but we "remember" it using a state (e.g. if the states of the TM are $q_1,q_2,..$ etc, we will move to $q_1^a$ if we see an a or to $q_1^c$ if we see a c, etc.)
Before putting the letter back to the queue we first we check the next letter, and if it is not the head, we put it back, If it is the head, we may move the head as needed.
The cycle of moving the head left will look something like the following:
a→bc$ ->(remember a using states)-> →bc$a -> bc& -> (*)
at this point the machine knows it needs to move the head to the left. It remembers a and so it put it back in the queue, now remembering b using the current state
-> c$→a -> $→ab -> ... -> →abc$
