3 ms·

The list in the 1st answer is amazing, but the 2nd highest answer has one of my favorite things: > Turing machines (we think) capture everything that's computa

by Adrock 13y ago

The list in the 1st answer is amazing, but the 2nd highest answer has one of my favorite things: > Turing machines (we think) capture everything that's computable. However, we can ask: What parts of a Turing machine are "essential"? What happens when you limit a Turing machine in various ways? DFAs are a very severe and natural limitation (taking away memory). PDAs are a less severe limitation, etc. It's theoretically interesting to see what memory gives you and what happens when you go without it. It seems a very natural and basic question to me. I like to think of it the other way, though. A DFA with a stack is a PDA. A DFA with two stacks is a Turing machine. Looking at the 3 different classes as DFAs with 0, 1, or 2 stacks is just so beautiful...

alok-g 13y ago
Adding to the above: While in most algorithms books, we treat integer operations (addition, multiplication) as an O[1] operation, most do not even mention that this is only because these integers are constrained in size to a limited number of bits. Storing an integer in mathematics would require infinite amount of memory. Analyzing the Big-O complexity of the algorithms is too much more fun when you take the integer fixed-width assumption out. A single integer can serve as a "stack" from the perspectives of computer science. Without loss of generalization, assume that the set of symbols has digits 1..9. Now push operation is multiplication by ten and addition of the digit, while pop is taking the units digit and dividing by ten. In other words, if you are using a single integer in your program, and do not want to simply return incorrect answers or throw exceptions due to overflow errors, then your algorithm may already be beyond an NDFA. This would for example happen if you are trying to match parenthesis in a string like "(()())(((())))". You can easily do this by having an integer in your program, reading the string from left to right, incrementing the integer when you encounter a '(' and decrement for a ')'. The computer science books would however show the above problem to be unsolvable using a NDFA. (You have solved the problem for all practical purposes since the strings you'll encounter may never be that long, but a computer with finite memory is in principle incapable of solving this "correctly" for all possible inputs.)
SandyPark 13y ago
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.

by Adrock 13y ago

alok-g 13y ago

Adding to the above: While in most algorithms books, we treat integer operations (addition, multiplication) as an O[1] operation, most do not even mention that this is only because these integers are constrained in size to a limited number of bits. Storing an integer in mathematics would require infinite amount of memory. Analyzing the Big-O complexity of the algorithms is too much more fun when you take the integer fixed-width assumption out. A single integer can serve as a "stack" from the perspectives of computer science. Without loss of generalization, assume that the set of symbols has digits 1..9. Now push operation is multiplication by ten and addition of the digit, while pop is taking the units digit and dividing by ten. In other words, if you are using a single integer in your program, and do not want to simply return incorrect answers or throw exceptions due to overflow errors, then your algorithm may already be beyond an NDFA. This would for example happen if you are trying to match parenthesis in a string like "(()())(((())))". You can easily do this by having an integer in your program, reading the string from left to right, incrementing the integer when you encounter a '(' and decrement for a ')'. The computer science books would however show the above problem to be unsolvable using a NDFA. (You have solved the problem for all practical purposes since the strings you'll encounter may never be that long, but a computer with finite memory is in principle incapable of solving this "correctly" for all possible inputs.)

SandyPark 13y ago

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.