Robert.Frederking%CMU-CS-CAD@sri-unix.UUCP (11/03/83)
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.
Jon.Webb@CMU-CS-IUS.ARPA (11/08/83)
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
HEWITT%MIT-AI@sri-unix.UUCP (11/11/83)
From: Carl Hewitt <HEWITT at MIT-AI> An excellent treatise on how some parallel machines are more powerful than all sequential machines can be found in Will Clinger's doctoral dissertation "Foundations of Actor Semantics" which can be obtained by sending $7 to Publications Office MIT Artificial Intelligence Laboratory 545 Technology Square Cambridge, Mass. 02139 requesting Technical Report 633 dated May 1981.