News for hackers. Stuff that matters.
Re:What is the enlightenment I'm supposed to attain after st... by SandyPark on Sunday November 24, 2013 @01:32PM (#6790491)
How is a Turing Machine a DFA with two stacks? I never learned it like that in my Theory of Computation course...
Re:What is the enlightenment I'm supposed to attain after st... by Adrock on Sunday November 24, 2013 @01:37PM (#6790508)
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.

Re:What is the enlightenment I'm supposed to attain after st... by chas on Sunday November 24, 2013 @06:01PM (#6791576)
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...

Re:What is the enlightenment I'm supposed to attain after st... by alok-g on Sunday November 24, 2013 @01:35PM (#6790501)
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...

Re:What is the enlightenment I'm supposed to attain after st... by programnature on Sunday November 24, 2013 @01:37PM (#6790509)
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.