quantum Computing
Perry E. Metzger
perry at imsi.com
Wed May 18 11:14:56 PDT 1994
Mike McNally says:
>
> 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.
Correct. The hierarchy as I remember it is roughly (from least to most
powerful in terms of size of the recognizable languages) FAs, PDAs
(that is, deterministic push-down automata), NPDAs, TMs. Its been a
while, but I seem to recall that non-deterministic pushdown automata
could recognise some languages that deterministic ones could not.
Perry
More information about the cypherpunks-legacy
mailing list