[13879] in Cypherpunks
Re: quantum Computing
daemon@ATHENA.MIT.EDU (Perry E. Metzger)
Wed May 18 14:37:54 1994
To: juola@bruno.cs.colorado.edu
Cc: cypherpunks@toad.com
In-Reply-To: Your message of "Wed, 18 May 1994 12:00:47 MDT."
<199405181800.MAA22999@bruno.cs.colorado.edu>
Reply-To: perry@imsi.com
Date: Wed, 18 May 1994 14:11:24 -0400
From: "Perry E. Metzger" <perry@imsi.com>
juola@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
