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