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