3 ms·
Non-deterministic Turing machines are still computationally equivalent to Turing machines. That is, there is no problem that a Non-deterministic Turing machine
by tsimionescu 4y ago
Non-deterministic Turing machines are still computationally equivalent to Turing machines. That is, there is no problem that a Non-deterministic Turing machine can solve for which there doesn't exist a deterministic Turing machine that solves it as well, and vice versa. Non-deterministic Turing machines are exponentially faster as far as we know (P ≠ NP seems to be true) but they are no more powerful. And note that Non-deterministic algorithms are far more powerful than anyone imagines human brains could be - as they can perform an infinite number of operations in parallel (equivalently, they have an oracle that gives them the best possible choice at any step).
Even worse for your argument, probabilistic Turing machines and algorithms (classical bounded-error probabilistic machines) don't even seem to be faster than fully deterministic ones (P = BEP).