Re:An Argument for P=NP (2005) [pdf]
by mikeash on Monday August 17, 2015 @04:59PM
(#10076074)
A nondeterministic Turing machine can be thought of as a machine that can try all possibilities at once. In this conception, it's the ultimate parallel computer. In this conception, the guess function is actually trying all possibilities for the number d, and if any of those possibilities is a match, it says so.
Another way of thinking about it is as pure magic. If there is a number that's a match, then that number comes out of the "guess" function somehow.
As for why we can't use a nondeterministic Turing machine to achieve what we want, it's because nobody knows how to build one. They're the computing equivalent of a frictionless pulley or a mathematical point: a useful abstraction, but not something you can actually construct. If anyone ever figures out how to send information back in time then it may be possible, but absent that we're stuck with the regular kind of Turing machine.
Another way of thinking about it is as pure magic. If there is a number that's a match, then that number comes out of the "guess" function somehow.
As for why we can't use a nondeterministic Turing machine to achieve what we want, it's because nobody knows how to build one. They're the computing equivalent of a frictionless pulley or a mathematical point: a useful abstraction, but not something you can actually construct. If anyone ever figures out how to send information back in time then it may be possible, but absent that we're stuck with the regular kind of Turing machine.