quantum Computing
Mike McNally
m5 at vail.tivoli.com
Wed May 18 11:03:55 PDT 1994
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 <m5 at tivoli.com> |
| TAKE TWA TO CAIRO. ||| Tivoli Systems, Austin, TX: |
| (actual fortune cookie) ||| "Like A Little Bit of Semi-Heaven" |
More information about the Testlist
mailing list