CDR: Re: Minesweeper and defeating modern encryption technology

[Jim Choate]

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