On Thu, Mar 3, 2011 at 12:21 PM, Stephen B. Gray <stevebg@roadrunner.com> wrote:
On 2 Mar 2011, at 23:02, Fred lunnon wrote:
This construction reminds me of the SWASC (Sealing Wax And String Computer) I concocted for an undergraduate course in algorithmics: to find the shortest path on a graph, first join up a bunch of strings cut to lengths representing roads, using wax blobs for the towns; then hold the start blob and finish blob in two hands and pull (but not too hard!).
This device finds any desired shortest path in constant time --- in contrast to (say) Dijkstra's algorithm, which costs time around n log n for n towns. But SWASC will never catch on because of the excessive resources required to configure / build your "computer" in the first place. These might just be worthwhile when the map is fixed and many routes are required --- but in the case of a single maze solution, it's hard to see how they could be justified.
Furthermore, claims for the performance of analogue methods depend on speed of component settling --- the authors give no indication of how fast current devices might be expected to operate. Compare "DNA" computers. [Note that Gene Salamin's suggestion for fabrication has not been copied to Jon Cartwright.]
Fred Lunnon
Is it possible to model the physics of pulling the blobs apart and get a constant-time algorithm?
Not with a single-processor computer; modeling the physics of N objects is going to take at least time proportional to N, not constant time. If there are potential interactions between each pair of object, it will take time N^2 unless you have some cleverness in your algorithm. Andy