Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!decvax!harpo!seismo!hao!hplabs!sri-unix!Robert.Frederking@CMU-CS-CAD
From: Robert.Frederking%CMU-CS-CAD@sri-unix.UUCP
Newsgroups: net.ai
Subject: Parallel vs. Sequential
Message-ID: <13321@sri-arpa.UUCP>
Date: Thu, 3-Nov-83 13:27:10 EST
Article-I.D.: sri-arpa.13321
Posted: Thu Nov  3 13:27:10 1983
Date-Received: Sun, 6-Nov-83 23:49:56 EST
Lines: 12

Re: Phillip Kahn's claim that "not ALL parallel computations can be made
sequential": I don't believe it, unless you are talking about infinitely
many processing elements.  The Turing Machine is the most powerful model of
computation known, and it is inherently serial (and equivalent to a
Tesselation Automaton, which is totally parallel).  Any computation that
requires all the values at an "instant" can simply run at N times the
sampling rate of your sensors: it locks them, reads each one, and makes its
decisions after looking at all of them, and then unlocks them to examine the
next time slice.  If one is talking practically, this might not be possible
due to speed considerations, but theoretically it is possible.  So while at
a theoretical level ALL parallel computations can be simulated sequentially,
in practice one often requires parallelism to cope with real-world speeds.