From: "Perry E. Metzger" <perry@imsi.com>
Date: Wed, 18 May 94 11:11:36 PDT
To: juola@bruno.cs.colorado.edu
Subject: Re: quantum Computing
In-Reply-To: <199405181800.MAA22999@bruno.cs.colorado.edu>
Message-ID: <9405181811.AA02932@snark.imsi.com>
MIME-Version: 1.0
Content-Type: text/plain



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