17 Dec
2003
17 Dec
'03
11:17 p.m.
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@tivoli.com> | | TAKE TWA TO CAIRO. ||| Tivoli Systems, Austin, TX: | | (actual fortune cookie) ||| "Like A Little Bit of Semi-Heaven" |