CDR: Re: Minesweeper and defeating modern encryption technology

[Jim Choate]

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 at ssz.com
       www.ssz.com            .',  ||||    `/( e\      512-451-7087
                           -====~~mm-'`-```-mm --'-
    --------------------------------------------------------------------