Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!watmath!clyde!caip!rutgers!lll-crg!seismo!columbia!heathcliff.columbia.edu!zdenek From: zdenek@heathcliff.columbia.edu (Zdenek Radouch) Newsgroups: sci.math Subject: Re: Analog models of computation Message-ID: <3529@columbia.UUCP> Date: Sat, 18-Oct-86 22:48:02 EDT Article-I.D.: columbia.3529 Posted: Sat Oct 18 22:48:02 1986 Date-Received: Tue, 21-Oct-86 22:46:12 EDT References: <8194@watrose.UUCP> <6490@think.COM> <3504@columbia.UUCP> 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: 48 In article <27@cartan.Berkeley.EDU> desj@brahms (David desJardins) writes: >In article <3516@columbia.UUCP> zdenek@heathcliff.columbia.edu.UUCP (Zdenek Radouch) writes: >> >>Sorry, you are wrong. To solve the problem you just lift the model! > > Sorry, you are doubly wrong. > > 1) From this point of view (solving a *particular* graph) a digital >computer can also do it in constant time. Determine the answer for that >particular graph, and then write a program to print it out. You are very confused about what it takes to find the shortest path between two vertices in a graph. We are not talking about building models or computers, drawing graphs, calculating distances, inputting data and printing results. We are talking about the actual methods of implementing a function: min(set of distances). In order to implement the function you have to use primitive operation COMPARE. It turns out, that relational operators in mathematics are always applied to TWO operands, hence your additional time if n>2. His model together with his eyes happen to perform FULL PARALLEL compare, therefore time = 1. As I said, his method might not be practical, but it's elegant and much faster. > 2) It takes linear time for the model to fall into place and indicate the >solution after you lift it. Only when you consider Grurmstipth's force acting on the beads. It's been known for years, at least in physics, that the time, n falling beads take to fall, is INDEPENDENT of n. > > -- David desJardins 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