Author: Robert Hyatt
Date: 21:04:46 10/03/01
Go up one level in this thread
On October 03, 2001 at 17:05:46, Sune Fischer wrote: >On October 03, 2001 at 16:28:15, Miguel A. Ballicora wrote: > >>>So we have reduced the problem to the following: >>>There exists a parallel algorithim, which in no way can be rewritten into a >>>serial one without increased "work". >>>This is now the point of disagreement, right? >> >>This is what I say: >>The possibility that somebody writes at one point an algorithm using two threads >>(parallel) that could faster than a similar using one has not been proven false >>yet. Of course you could "serialize it" but in theory this could either 1) >>create some overhead or 2) be very inconvenient to rewrite (like recursion is >>not always convenient to be rewritten). I do not see that this hypothetical >>situation would violate any "law". >> >>Regards, >>Miguel > >Well, we are not as far apart as I initially thought;) >This is not in direct violation to any physics I know either (as far as I can >see). >It was the >2 discussion that made my eyes pop out. > >I suppose it is hard to prove that there are _no_ algorithms where using >multiple threads would be convenient. > >-S. \ The proof is trivial, and is given in almost any good book on automata theory. It has to do with the proof of the theorem: Theorem: any computation that can be done using a two-tape turing machine can be done on a one tape turing machine. This can be proven, and the idea is directly analogous to a two-processor vs one processor turing machine. Our undergraduates here could certainly prove it after taking the course. Our graduate students see it a second time and could prove it as well. I could recite the proof if needed, but finding any theory book would save a lot of typing by me, and reading by others...
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.