CDR: Re: Minesweeper and defeating modern encryption technology

[Bill Stewart]

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:
>
>http://www.hissa.nist.gov/dads/HTML/nondetrmtur.html

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 at pobox.com
PGP Fingerprint D454 E202 CBC8 40BF  3C85 B884 0ABE 4639