At 07:34 AM 11/6/00 -0600, Jim Choate wrote:
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:
It's actually http://hissa.nist.gov/dads/HTML/nondetrmtur.html with no www.
"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.
You're still not getting what the non-deterministic Turing machine does. The problem is structured as a decision-making problem, where an input is "accepted" if the Turing machine halts in an accept state, meaning the set of input is a valid solution to the problem (sometimes leading to ugly convoluted problem definitions if you're really trying to find an optimum rather than a yes-no problem like a Hamiltonian or 3-SAT), or rejected if it halts in a rejection state (where the proposed answer is not a valid solution), or doesn't halt (if it's an annoying problem+input.) "An input is accepted if any move sequence leads to acceptance" means that there's some collection of next states (bits of answer) that leads to the an accept state. How do you know _which_ input value leads to acceptance? That's the magic part. If there are N bits of input, there are 2**N possible move sequences, of which the existence of one correct sequence leads to acceptance.
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).
I don't think anybody's claimed that it has - the Satisfiability problem and the subset 3-SAT problem don't deal with all Boolean problems, just ones with a particular form. Thanks! Bill Bill Stewart, bill.stewart@pobox.com PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639