CDR: Re: Minesweeper and defeating modern encryption technology

[Sampo A Syreeni]

On Mon, 6 Nov 2000, Jim Choate wrote:

>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.

The whole idea of NDTM's arises from parallelism - having the correct answer
and validating it is equivalent to having all the answers and validating
them in parallel, producing one or more correct ones.

>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.

Remember that we are not quantifying over the set of boolean expressions but
over the set of possible inputs to a given, finite one.

Sampo Syreeni <decoy at iki.fi>, aka decoy, student/math/Helsinki university