cryptoanarchy.wiki

Arise, you have nothing to lose but your barbed wire fences!

1994-05-18 - Re: quantum Computing

Header Data

From: “Perry E. Metzger” <perry@imsi.com>
To: m5@vail.tivoli.com (Mike McNally)
Message Hash: cecae9f25668c52493a8e8277def8c51fdaf88f85458c0c3b3b3ad032fc14cdc
Message ID: <9405181814.AA02946@snark.imsi.com>
Reply To: <9405181803.AA11052@vail.tivoli.com>
UTC Datetime: 1994-05-18 18:14:56 UTC
Raw Date: Wed, 18 May 94 11:14:56 PDT

Raw message

From: "Perry E. Metzger" <perry@imsi.com>
Date: Wed, 18 May 94 11:14:56 PDT
To: m5@vail.tivoli.com (Mike McNally)
Subject: Re: quantum Computing
In-Reply-To: <9405181803.AA11052@vail.tivoli.com>
Message-ID: <9405181814.AA02946@snark.imsi.com>
MIME-Version: 1.0
Content-Type: text/plain



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

Thread