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.physics,sci.math Subject: Re: Analog models of computation Message-ID: <3504@columbia.UUCP> Date: Wed, 15-Oct-86 20:18:08 EDT Article-I.D.: columbia.3504 Posted: Wed Oct 15 20:18:08 1986 Date-Received: Thu, 16-Oct-86 00:00:28 EDT References: <8194@watrose.UUCP> <6490@think.COM> Sender: nobody@columbia.UUCP Reply-To: zdenek@heathcliff.columbia.edu.UUCP (Zdenek Radouch) Followup-To: sci.bs Distribution: net Organization: Columbia University CS Department Lines: 109 Summary: It's not the model, it's you. Xref: mnetor sci.physics:10 sci.math:4 In article <6490@think.COM> bradley@godot.think.com.UUCP (Bradley Kuszmaul) writes: >In article <8194@watrose.UUCP> rpjday@watrose.UUCP (rpjday) writes: >> >> I am interested in collecting examples of problems in the area of >>computation that are generally acknowledged to be reasonably to >>obscenely difficult using the digital computer model, but which have >>simple elegant solutions if one was allowed to construct some form >>of "analog" computer. >> As an example, the problem of finding the shortest path between two >>points in a graph is easily solved if one is allowed to build a string >>model of the graph, then pick it up by the source node, and measure the >>distance straight down to the target node. I'm sure everyone is familiar >>with this trick, but I'm also sure there were other "analog" models >>of computation, some for supposedly intractable problems. >> ... >>R Day > >Summary of the rather long article which follows: > (1) Finding the distance betwen two points in a graph can be solved > efficiently on a digital computer. > (2) The analog computer you propose must grow as fast as the > problem (the crane to lift the string must grow). If I am > allowed to build a digital computer which also grows then I can keep > up with your analog computer by exploiting parallelism (e.g. > using a Connection Machine (tm) computer system.) > (3) The analog computer you propose does not even work. 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. Do you not like his example? It reminds me the recent FTL disscussion, that ended up with several net.physics readers concluding that all the confusion was caused by "massless and infinitely rigid rods" and similar objects, that can't really exist. It's not the models, what counts. It is HOW they get used! Summary of the rather long flame which follows: (1) You didn't convince me, that it would be more efficient for ME to use the computer insted of the strings. (2) The machine has to grow only because YOU made it too small in the first place. (3) The fact, that you can't add 2.3*10^456 + 1.2*10^789 on your calculator doesn't mean, that the calculator doesn't work. >I don't beleive that your example satisfies the requirements. Finding >the shortest path between two points using a digital computer is >nowhere near obscenely difficult.... > [The algorithm and its analysis deleted] Well, you needed 18 lines to describe the algorithm and 10 lines to explain it. He needed 25 words to describe his method. Then again, maybe I don't know what "simple and elegant" really means. >.... In fact it can be done in time >which is only logarithmically worse than linear in the size of the >graph by the following algorithm: His machine solves the problem in a time unit. I don't care if the time to run the algorithm is logarithmically worse than linear or exponentially better than quadratic. The algorithm is SLOWER! >.....For example, it >takes a rather large hoist to implement the algorithm for billion >vertex graphs......... > > For the digital computer, the corresponding growth is in the memory >components, but if your are going to charge me for the memory in my >digital computer, I will respond by replacing every memory chip with a >microprocessor chip, so that I can exploit parallelism too. Gee, that's really good idea! Replace every memory chip with a microprocessor chip in order to exploit parallelism! >Then we get into an analysis of the performance of parallel algorithms to do >the same thing, and what kind of interconnection network we are >assuming between the processors... One thing is for sure. The interconnection network has to be good enough to hold data for the bilion vertex graph... >Another problem with the analog approach to solving this problem is >that it does not work.... >The fact that the string has finite thickness is going to get us. Whereas the fact, that the word in Connection Machine (tm) computer system has finite length, is going to get martians. > - bradley@think.com or think!bradley The second one is more appropriate. zdenek ------------------------------------------------------------------------- Men are four: He who knows and knows that he knows, he is wise - follow him; He who knows and knows not that he knows, he is asleep - wake him; He who knows not and knows that he knows not, he is simple - teach him; He who knows not and knows not that he knows not, he is a fool - shun him! zdenek@CS.COLUMBIA.EDU or ...!seismo!columbia!cs!zdenek Zdenek Radouch, 457 Computer Science, Columbia University, 500 West 120th St., New York, NY 10027