[13873] in Cypherpunks
Re: quantum Computing
daemon@ATHENA.MIT.EDU (Mike McNally)
Wed May 18 14:16:38 1994
Date: Wed, 18 May 94 13:03:43 CDT
From: m5@vail.tivoli.com (Mike McNally)
To: Rick Busdiecker <rfb@lehman.com>
Cc: cypherpunks@toad.com
In-Reply-To: <9405181756.AA14881@fnord.lehman.com>
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" |
