From: Mick Newsgroups: comp.theory,sci.math Subject: Re: Solving problems via laws of nature Date: Wed, 19 Nov 1997 10:41:05 +0100 Matthew Fletcher wrote: > What mathematical problems can be solved instantly by using some natural > minimisation feature? Could a class of such solvable problems be > determined? Is there any work on this? A.K.Dewdney in "The New Turing Omnibus" (1993) discusses examples of physical models of analog computation, including the one to which you refer. It's in Ch. 33, "Spaghetti Computers". Also there is a book by C.Isenberg "The Science of Soap Films and Soap Bubbles" (1978). Other examples cited by Dewdney are: 1. sorting numbers using a bunch of dried spaghetti trimmed to lengths representing the numbers -gather them up and slam them end down on a desk -sorted! 2. finding the shortest path in a graph. Knot together lengths of string to make a net representing the graph, grab (any) two nodes in question and pull apart -shortest path is represented by the tightest section of string. 3. finding the boundary of minimum area enclosing a set of points (convex hull) using nails hammered into a board representing the points, then stretch a rubber band around them. 4. a pair of lasers, a detector, and a pair of parallel mirrors can be used to identify prime numbers (don't ask!) I remember as a child, finding the area under a curve by cutting out a representation of it, and weighing it. Dewdney says there may be other examples "part of computer science folklore, passed around by word of mouth and rarely described in the literature". He also observed that the only case he encountered where the analog solution sometimes failed, "just happened" to be NP-complete; and finished with the remark that we would be wise to remind ourselves that digital computers may be only a step towards more powerful computational devices embodying new principles we have not yet dreamed of. Hmmm. It seems to me that there must be a very large or infinite number of natural machines such as the examples given, especially if we include the inefficient ones. Hey, isn't every physical object an answer to a "question" posed implicitly by nature, rather than explicitly by ourselves? My interest in all of this is that organisms may be considered computational devices for answering questions posed by their natural environment. We may soon know enough about biology -genetics, molecular biol, phisiology, ecology- to construct a continuous chain of understanding of natural information processing in organisms from the simplest replicating molecules all the way up to consciousness. If we could represent biological information processing in a simple organism in a suitably abtract Turing -like (?) way, it should work for any organism, and possibly for all other natural machines too. Michael Pocklington mick@blankley.prestel.co.uk