p.s. - A couple more interesting links:
http://www.scottaaronson.com/papers/npcomplete.pdf (question: anybody out there tried "anthropic computing"? :-) and (some of what prompted the above): http://kryten.mm.rpi.edu/scb_pnp_solved22.pdf (consider the risks of careless reading . . . could this be a new entry in the "next Sokal" sweepstakes?) tom On Mar 25, 2010, at 12:49 AM, Tom Carter wrote: > 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 > ============================================================ 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
