4 ms·
Do not confuse nondeterministic Turing machines with nondeterministic (finite) state machines/automata. The latter are proven to be equivalent to their determin
by frabert 6y ago
Do not confuse nondeterministic Turing machines with nondeterministic (finite) state machines/automata. The latter are proven to be equivalent to their deterministic counterparts, the former are not.
- jcranmer 6y agoA nondeterministic Turing machine is no more powerful than its deterministic Turing machine, if you define "powerful" as "can solve problems." If you instead define "powerful" as "can solve problems within a given amount of time," then there may be a distinction. Put another way, you can simulate a nondeterministic Turing machine with a deterministic one, just as you can simulate a nondeterministic finite-state machine with a deterministic one. However, this simulation does come with increased time and space requirements.