On Sun, 5 Nov 2000, Bill Stewart wrote:
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.
Dave's right, Jim. The NDTM obtains The Right Answer by using a process you could call "guessing" or you could call "an oracle". That's not "Oracle" like "Larry Ellison telling you what you WILL buy next", it's "Oracle" like "Stoned priestess telling you that if you attack today, a great kingdom will fall", and the polynomial-time part is where you crank that through and find out that yes, it's correct. (Unfortunately it's *your* kingdom, but it's correct.)
Dave's right, you're not. While it is true a NDTM has a guessing module before that 'guessed' state causes the NDTM to change to the resultant state there is a level of PROOF involved. It is required to prove the answer is right. There is NO magic in an NDTM, it doesn't pull the correct answer out of the air. The distinction at this level between a NDTM and a probabilistic TM is that a PTM doesn't check the result at time of selection but after. It's the algorithm that the Turing machine is running that does the checking. In a NDTM it is the 'guessing module'. 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. See: http://www.hissa.nist.gov/dads/HTML/nondetrmtur.html "Definition: A turning machine which has more than one next state for some combination of contents of the current cell and current state. An input is accepted if any move sequence leads to acceptance." In other words you have to have a 'input verifier' that verifies the data is good before the next state(s) are entered. Note this means your verification function can't be NP. 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. It most assuradely has NOTHING to do with the question of how one builds a 'universal sentence parser' that can return a verifiable yes/no as to validity when Godel's says all sentences don't necessarily have a valid result (ie they aren't provably consistent). ____________________________________________________________________ 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 --'- --------------------------------------------------------------------