On Mon, 6 Nov 2000, Jim Choate wrote:
The real question related to a NDTM is 'if you have a algorithm that allows you to guess answers and verify them before submission for execution' why are you executing the algorithm? You already know the answer is correct.
The whole idea of NDTM's arises from parallelism - having the correct answer and validating it is equivalent to having all the answers and validating them in parallel, producing one or more correct ones.
This is all really moot since NDTM's don't handle a single language that a DTM can handle, and determining whether all Boolean sentences are valid (irrespective of their actual result) is dealing with a language.
Remember that we are not quantifying over the set of boolean expressions but over the set of possible inputs to a given, finite one. Sampo Syreeni <decoy@iki.fi>, aka decoy, student/math/Helsinki university