Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!security!genrad!decvax!harpo!seismo!hao!hplabs!sri-unix!Jon.Webb@CMU-CS-IUS.ARPA
From: Jon.Webb@CMU-CS-IUS.ARPA
Newsgroups: net.ai
Subject: parallel vs. sequential
Message-ID: <13500@sri-arpa.UUCP>
Date: Tue, 8-Nov-83 09:26:00 EST
Article-I.D.: sri-arpa.13500
Posted: Tue Nov  8 09:26:00 1983
Date-Received: Sat, 12-Nov-83 14:40:35 EST
Lines: 13

Parallel and sequential machines are not equivalent, even in abstract
models.  For example, an absract parallel machine can generate truly
random numbers by starting two processes at the same time, which are
identical except that one sends the main processor a "0" and the other
sends a "1". The main processor accepts the first number it receives.
A Turing machine can generate only pseudo-random numbers.

However, I do not believe a parallel machine is more powerful (in the
formal sense) than a Turing machine with a true random-number
generator.  I don't know of a proof of this; but it sounds like
something that work has been done on.

Jon