quantum Computing

Perry E. Metzger perry at imsi.com
Wed May 18 11:11:36 PDT 1994



juola at bruno.cs.colorado.edu says:
>   Mike McNally responds:
>   >While we're being picky, I'll point out that (unless I'm wrong of
>   >course) it's not really an NFA, but a non-deterministic Turing
>   >machine (an "NTM"?) that's the automaton at issue here.
>   
> That is correct.  As a matter of fact, it's an easy theorem that
> an NFA has the same computing capacity as a DFA; it is not known
> whether this theorem holds for more powerful machines, and is in
> fact the heart of the P ?= NP conjecture.

The terms you are using are ambiguious. NTMs are no more powerful than
deterministic TMs. They are possibly faster, but there are no
languages that NTMs can recognise that deterministic TMs cannot
recognise. It is hypothesized (though more or less unprovable) that
there is no more powerful model of computation than Turing machines in
the sense of what operations can be performed. Speed is again, as I
noted, a different matter.

Perry






More information about the cypherpunks-legacy mailing list