3 ms·

How is a Turing Machine a DFA with two stacks? I never learned it like that in my Theory of Computation course...

alok-g 13y ago
See Ullman's book [1] for more details on formal proofs. Basically you can emulate the Turing machine's tape on the left side of the head with one stack and on the right side with the second stack. An important question to now ask would be what happens if the tape in the machine has more than two directions; say for example it has a two-dimensional tape. The head may move left, right, but also up and down. It can be proven that such a machine would not be any more capable than the Turing machine with a 1D tape. Again see Ullman's book for details. [1] http://www.amazon.com/Introduction-Automata-Theory-Languages-Computation/dp/0321455363/ http://www.amazon.com/Introduction-Automata-Theory-Languages...
Adrock 13y ago
The informal answer is that you can treat two stacks like one tape. The top of the first stack is the current location on the tape. You can move the tape head to the left by popping from Stack 1 and pushing that value onto Stack 2. Pop from Stack 2 and push on Stack 1 to move to the right. What's really funky is that a DFA with a queue is a Turing machine. You can show this by putting a sentinel value in the queue that separates two stacks and having some crazy loop structures that allow you to push and pop from the two stacks it represents.
- chas 13y ago
  Another way of saying this is that the two stacks as a list zipper[1], which makes the correspondence between a DFA with arbitrarily writable memory and a DFA with two stacks readily apparent. [1]http://en.wikipedia.org/wiki/Zipper_(data_structure)#Example:_Bidirectional_list_traversal http://en.wikipedia.org/wiki/Zipper_(data_structure)#Example...
programnature 13y ago
split the tape into 2 halves; the tape to the left of the head is one stack, the tape to the right of the head is the other stack. Head moving long the tape is just popping from one stack and pushing onto the other. The head state (and other bookkeeping) can be encoded in the DFA.

See Ullman's book [1] for more details on formal proofs. Basically you can emulate the Turing machine's tape on the left side of the head with one stack and on the right side with the second stack. An important question to now ask would be what happens if the tape in the machine has more than two directions; say for example it has a two-dimensional tape. The head may move left, right, but also up and down. It can be proven that such a machine would not be any more capable than the Turing machine with a 1D tape. Again see Ullman's book for details. [1] http://www.amazon.com/Introduction-Automata-Theory-Languages-Computation/dp/0321455363/ http://www.amazon.com/Introduction-Automata-Theory-Languages...

Adrock 13y ago

The informal answer is that you can treat two stacks like one tape. The top of the first stack is the current location on the tape. You can move the tape head to the left by popping from Stack 1 and pushing that value onto Stack 2. Pop from Stack 2 and push on Stack 1 to move to the right. What's really funky is that a DFA with a queue is a Turing machine. You can show this by putting a sentinel value in the queue that separates two stacks and having some crazy loop structures that allow you to push and pop from the two stacks it represents.

chas 13y ago
Another way of saying this is that the two stacks as a list zipper[1], which makes the correspondence between a DFA with arbitrarily writable memory and a DFA with two stacks readily apparent. [1]http://en.wikipedia.org/wiki/Zipper_(data_structure)#Example:_Bidirectional_list_traversal http://en.wikipedia.org/wiki/Zipper_(data_structure)#Example...

programnature 13y ago

split the tape into 2 halves; the tape to the left of the head is one stack, the tape to the right of the head is the other stack. Head moving long the tape is just popping from one stack and pushing onto the other. The head state (and other bookkeeping) can be encoded in the DFA.