[13877] in Cypherpunks
Re: quantum Computing
daemon@ATHENA.MIT.EDU (Perry E. Metzger)
Wed May 18 14:25:49 1994
To: m5@vail.tivoli.com (Mike McNally)
Cc: Rick Busdiecker <rfb@lehman.com>, cypherpunks@toad.com
In-Reply-To: Your message of "Wed, 18 May 1994 13:03:43 CDT."
<9405181803.AA11052@vail.tivoli.com>
Reply-To: perry@imsi.com
Date: Wed, 18 May 1994 14:14:41 -0400
From: "Perry E. Metzger" <perry@imsi.com>
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
