K'nex computation - using K'nex, a construction toy system, to build logic circuits. For a computer architecture project, these guys built logic gates with K'nex pieces operated by balls, culminating in a 4-bit adder with decimal decoder. It looks like they had more ambitious plans but their project was becoming complex to implement and hard to demonstrate. They have a video of the calculator in operation, and it's also worth going through the archives to read about how bits are represented (by ball position), how gates are implemented (with nice animations), and also their half- and full-adders (also with videos).
Source New Scientist Tech blog.
You know that Friday afternoon feeling. You should be working, but perhaps nothing too taxing. There's a couple of hours of "work" time left; it wouldn't be a good idea to start on something new just before the weekend.
Last Friday I found myself reading NP-complete Problems and Physical Reality. Apologies to those without a background in Computer Science—this relates to an unsolved problem in one of the most fundamental areas of computer science. In a nutshell, there are two classes of problems called P and NP; problems in P are amenable to solution by mechanical means, whereas problems in NP do not appear to be. That is, as far as we know, problems in NP take astronomical amounts of time to solve generally. However nobody has yet been able to prove that either P=NP or P≠NP. And this could be considered one of the most important open problems in mathematics. Or at least, there's one million dollars riding on it.
Unsurprisingly this big open question attracts a fair number of cranks. However, some of the more outlandish suggestions are quite interesting. The above paper deals with various suggestions that the physical universe may admit some efficient solutions to NP-complete (i.e. apparently hard) problems. Computation with unusual quantum computers, time travel, success-or-death and the famous soap bubbles. Worth a read if you've that kind of mind, the paper is well-written (and is the first paper I've read which cites itself).
One possibly bold suggestion is that the assumption that P≠NP should guide the development of physical theories. I like this. If your new kind of physics allows us to suddenly solve "hard" computations without breaking a sweat, perhaps we should be skeptical? And if you can't define an equivalent model of computation in your new theory, well perhaps it could do with some time to mature.
modified 14 March 2005 (13:37) 
