Owen - An interesting paper on some of these issues (you may recognize the author :-) :
http://eprints.kfupm.edu.sa/36302/1/36302.pdf But, possibly more fun: http://books.google.com/books?id=XW7fICYtkg8C&pg=PA223&lpg=PA223&dq=spaghetti+dewdney&source=bl&ots=fXNU7klBKJ&sig=z3hibL7KkO-WG1ewPLzfNn9HmxU&hl=en&ei=7wqrS9-oNIT6sgPsj_TPDQ&sa=X&oi=book_result&ct=result&resnum=2&ved=0CAkQ6AEwAQ#v=onepage&q=&f=false (if that link is too messy, google spaghetti dewdney , and click the google books link for The (new) Turing omnibus) Some exercises: 1.) Design a device to find the maximum of a set of real numbers in 1 step. (hint: spaghetti) 2.) Find the maximum length path in a tree in 2 steps. 3.) Evaluate the validity of this algorithm for finding the maximum (no loops) path between two given vertices in a connected graph: a. Make the graph out of string/wire (see Dewdney . . .) b. Hold the two vertices, one in each hand, and pull taut. Cut one (taut) link that doesn't separate the graph. c. Repeat step b. until there are no more links that can be cut without separating the graph. d. The remaining taut line between the two vertices is the desired path. (or is it???) Note: How can you make sure that cutting a particular link doesn't separate the graph? (hint: wire . . . :-) For the more philosophically inclined: http://homepages.ipact.nl/~lokhorst/hypercomputationUCL.pdf And, a reference link for the future: http://www.mdpi.com/journal/computers/special_issues/analogcomp tom On Mar 24, 2010, at 9:25 PM, Owen Densmore wrote: > In our Mathematical Thinking seminar (on computer science) today, the topic > of Analog computing came up. > > Do we have a good foundational approach to analog computing? For example, > analog automata, computational theory on decidability for analog computers, a > notion of analog computational complexity? > > -- Owen > > > > ============================================================ > FRIAM Applied Complexity Group listserv > Meets Fridays 9a-11:30 at cafe at St. John's College > lectures, archives, unsubscribe, maps at http://www.friam.org > ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org
