[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: quantum Computing




Rick Busdiecker writes:
 > No, NFA is acceptable and correct, it's Non-determinisic Finite
 > Automaton.  A non-deterministic Turing machine is a perfectly
 > reasonable example, however.

Uhh, isn't it the case that a Turing machine can simulate an NFA, but
not the reverse?  An NFA has no tape, and therefore is not as powerful
an automaton as a Turing machine.  Thus an NFA can be implemented by
an NTM, but not the reverse.

I think.

--
| GOOD TIME FOR MOVIE - GOING ||| Mike McNally <[email protected]>       |
| TAKE TWA TO CAIRO.          ||| Tivoli Systems, Austin, TX:        |
|     (actual fortune cookie) ||| "Like A Little Bit of Semi-Heaven" |