X-Message-Number: 8561
Date: Mon, 08 Sep 1997 10:03:46 -0400
From: "John P. Pietrzak" <>
Subject: Re: Photocopying Picasso
References: <>

Peter Merel wrote:
> Thomas Donaldson writes,
> 
> >Since we are quite parallel ourselves,
> >whatever we are uploaded into should also be at least as parallel.
> 
> Parallelism can be emulated trivially on a serial machine;
> non-determinism, however, cannot.

Actually, that's not quite true.  One can prove that there is an
equivalent deterministic finite state automata for each
non-deterministic finite state automata.  And, in fact, there is also
a proof that for each non-deterministic Turing Machine, there is an
equivalent deterministic Turing Machine.  (I guess it depends on what
sort of non-determinism you are thinking about.)


John

Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=8561