Re:Gödel's Theorem
by duckerude on Thursday January 31, 2019 @02:17PM
(#19047795)
Any NFA can be reduced to a DFA (potentially at the cost of exponential blowup), and any DFA is also a NFA. That's not really a bijection, but it's true that they're equivalent.
DFAs can run in bounded time, because every symbol takes exactly one step to be processed, and there is only one way to process a string.
That also means NFAs can run in bounded time, by reducing them to DFAs first, but that's not a very satisfying explanation.
A NFA rejects a string if it can not end in an accepting state. It's not intuitively straightforward to see whether that's the case, but it can be done in bounded time by exhaustively checking possible paths (which is possible with a finite number of states and a finite input string).
You can't always perform that trick with Turing machines, because they can have infinitely many reachable states.
DFAs can run in bounded time, because every symbol takes exactly one step to be processed, and there is only one way to process a string.
That also means NFAs can run in bounded time, by reducing them to DFAs first, but that's not a very satisfying explanation.
A NFA rejects a string if it can not end in an accepting state. It's not intuitively straightforward to see whether that's the case, but it can be done in bounded time by exhaustively checking possible paths (which is possible with a finite number of states and a finite input string).
You can't always perform that trick with Turing machines, because they can have infinitely many reachable states.