On Sun, 5 Nov 2000, dmolnar wrote:
There is no guarantee that a NDTM will guess the correct answer at any stage. The question the NDTM answers over a DTM is "Is there a statistical algorithm that is more efficient than a deterministic one?".
Um, the definition of "nondeterministic Turing machine" implies such a guarantee. You seem to be thinking of a probabilistic Turing machine - a machine which can flip coins and use the results in an algorithm. They are **not** the same thing.
??? A NDTM has a stage which if given correct input will cause the result to have one of several states (e.g. A Turing machine that holds both roots of a quadratic at the same time). However, we're right back to 'provably correct' which can't occur, even in principle because there are some legitimate input states that can't be resolved as 'correct'. I wasn't the one who injected 'guessing' in there (which a NDTM doesn't do, ever. It takes the next state only after a 'proof of correctness' step.). When the 'guess' factor is injected then you get a probabilistic NDTM. Which is what I was addressing. As to your assertion that they aren't the same thing, they can certainly be combined. Which was my interpetation of the 'guess an answer and prove it' and 'using a NDTM'. To me that implied a probabilistic NDTM, and that is what I ran with. Within the context of a universal set such as "all Boolean equations" it is clear that the distinction between a NDTM and a DTM is irrelevant. It goes back to the fact that NDTM can be shows to handle no languages that a DTM can resolve. So injecting a NDTM into the mix does nothing to change the results. In addition a NDTM has little worth in a world where we postulate all possible Boolean sentences are resolvable. It, after all, allows a state to be both 1 and 0, clearly contrary to our assertion. What one would want is to show that a DTM was all that is required to resolve any of those Boolean equations. Which can't be done if we accept the NDTM <-> DTM proof. ____________________________________________________________________ He is able who thinks he is able. Buddha The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage@ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------