Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!mnetor!seismo!columbia!heathcliff.columbia.edu!zdenek From: zdenek@heathcliff.columbia.edu (Zdenek Radouch) Newsgroups: sci.math Subject: Re: Analog models of computation Message-ID: <3516@columbia.UUCP> Date: Thu, 16-Oct-86 23:55:36 EDT Article-I.D.: columbia.3516 Posted: Thu Oct 16 23:55:36 1986 Date-Received: Fri, 17-Oct-86 03:38:19 EDT References: <8194@watrose.UUCP> <6490@think.COM> <3504@columbia.UUCP> <23@cartan.Berkeley.EDU> Sender: nobody@columbia.UUCP Reply-To: zdenek@heathcliff.columbia.edu.UUCP (Zdenek Radouch) Followup-To: sci.math Distribution: net Organization: Columbia University CS Department Lines: 62 Summary: Doesn't solve giga-node graph but is elegant. In article <23@cartan.Berkeley.EDU> desj@brahms (David desJardins) writes: >In article <3504@columbia.UUCP> zdenek@heathcliff.columbia.edu.UUCP (Zdenek Radouch) writes: >>Sorry, my friend, you totally missed the point. The author of the original >>posting brought up a very interesting idea, namely, that some problems can >>be solved more efficiently on machines that are NOT digital computers. >>He has chosen an example to illustrate, what he's looking for, and he >>certainly got his idea across. > > I'm afraid not. Not to me anyway. Ok. I was wrong. >To me this example is a perfect illus- >tration of why analog computing is so spectacularly unsuccessful. Be honest: >if you wanted to solve the shortest-path problem for a graph of 1000 vertices >and 100000 edges, would you prefer to use the analog or the digital method? No. But neither me nor he suggested, that the method should be used for large graphs. I think the method itself (the principle) is very elegant. Remember how Gauss added all the integers from 1 to n? He simply noticed, that 1 + n = 2 + n-1 = 3 + n-2 etc... That is what I call elegant. >It seems obvious that the analog method is completely hopeless -- you could >spend many days building special-purpose hardware to solve the one particular >problem, or you could solve it in a few minutes (an hour at most, including >the time to write the code) on a desktop computer, with a general algorithm >that can be used to solve *all* shortest-path problems, not just a particular >one. I can see, we are talking about two different things. Maybe he hasn't chosen the greatest example, maybe I misunderstood his intent. This is how I under- stand his example: Somebody gives you a graph and wants to find the shortest path. There are many ways to solve the problem. Let's consider these two: 1. Introduce mathematics (coordinates, distances, sorting etc....). Build a machine that can use it (digital computer). Solve the problem. 2. Make the graph out of strings and beads (duplicate the picture). Lift the model. As I said, I consider (2) to be elegant. Notice that you can figure out the shortest path without understanding the concept of distances, you don't even know, what the length of the shortest path is! Clearly, if you used a computer, you had to calculate the distances and that is something nobody asked for. The question was WHICH one is the shortest, not how long is the shortest path. Now, I am not saying that the method is general, let alone practical. It's just DAMN simple! >>His machine solves the problem in a time unit. > > Again, *nonsense*. It takes at least one time unit per edge to adjust >the length of the string to the specified value. Sorry, you are wrong. To solve the problem you just lift the model! zdenek P.S. I hate when somebody says "the model is bad". The models are fine; you just have to use them right!