Re: quantum Computing

Rick Busdiecker writes:
   > Not true.  What that means is that a polynomial time solution exists
   > for an NFA.  The only part has not been shown.
  
  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.

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