28 SEPTEMBER 2006
From the math-actually-is-important department, here is today's problem: How do you program a computer if you're clueless about its innards?
Think about it. Today's computer chips are carefully designed with elaborate
circuitry, so that a program written in a standard language will tell them
what to do. But suppose 
you have a computer chip hidden inside an impenetrable
black box, made not by Intel but by a mad nanoscientist who defies you to figure
out how to make it work.
It's not a screenplay for the next mad scientist movie (although that might be a good idea -- all rights reserved). In fact, it's a real-life scenario from the not too distant future.
To get faster and more powerful, computers need smaller and smaller components, which unavoidably means entering the realm of the nanoworld. Computer chips of the future will be covered by molecule-sized switches that convert inputs into outputs, which is, after all, what computing is all about.
Making such chips will be difficult, though. Even if you could figure out how to connect nanoswitches in precisely the right patterns, mass production with such small-scale precision would almost surely be prohibitively costly. It would be a lot cheaper to just dump molecules on a chip at random and see whether they can compute.
And that is exactly what might happen, say NASA scientists John Lawson and David Wolpert.
Nanochemists have plans for making molecules (or other nano-sized structures) that would organize themselves into linked networks, so that an electronic signal transmitted from one could influence another. Each molecular-sized switch would be either turned on (to send a signal) or off, depending on the signals it got from all the other switches it was connected to.
The question is, do you need to know how the switches are linked to program the chip to do what you want? The answer is no, say Lawson and Wolpert, of NASA's Ames Research Center in Moffett Field, Calif. All you need are some wires leading to and from the chip. Some wires would be for input -- providing the information needed to begin the computation. Other wires would provide output -- signals giving the answer to the computation. And a third set of wires would provide pathways to send in electrical voltage signals that "control" the computation.
To think about it in the simplest terms, imagine a chip that provides one output signal in response to two input signals. (Computer jargon: this sort of thing is called a logic gate). Let's say if you put in two 0s, you want to get a 0 out; if you put in a 1 and a 0, you want to get a 1. If you don't know how the switches are connected, it would seem hopeless to try to program them to compute those answers correctly. But if you send various voltages in via the control wires, the chip might start getting the right answers more often than not. Your goal, of course, is to get right answers all the time -- that is, keep the errors to an absolute minimum.
In a new paper, Lawson and Wolpert show how to write down a formula for making the error rate a minimum (ideally, zero). The inputs, outputs and control voltages are all represented in the equation. Computer simulations show how the equation can guide the choice of control voltages, ultimately finding a set of voltages that programs the chip to get the right answers.
In the simulations, each control wire acts as an independent "agent," trying out different voltages to seek the ones that get the error rate closer to zero. (Each agent "learns" to do better as the process progresses, basing new voltage choices on how well previous choices worked.)
Lawson and Wolpert's simulations show that different control agents, working independently, really can arrive at a set of signals that makes the chip get the right answer a high percentage of the time. In other words, the control agents solve the equation for minimizing mistakes, using a mathematically sophisticated form of trial and error.
This approach has lots to offer. Suppose one of the switches on the chip gets stuck (either on or off) or switches from on to off no matter what signals it gets. The control agents will see that the errors are increasing and adjust themselves to make the chip get the right answers again.
That means that the manufacturing process does not have to be perfect -- chips with flaws can still be programmed to work correctly. And these chips could be cheaper to make anyway -- they can assemble themselves randomly, so you wouldn't have to pay high design costs.
"With a random assembly process, large batches of chips might be produced very inexpensively," Lawson and Wolpert note in their paper, published recently in the Journal of Computational and Theoretical Nanoscience.
A more important lesson than finding a way to save money, of course, is appreciating math's usefulness for solving really hard problems. Knowing how to write down equations is a powerful tool for clear thinking. After all, the human brain itself is a sort of computer in a black box. Understanding something about math is an excellent way to unleash the brain's computing capability. And to make computing machines ever more powerful, the human brain will have to do some improving, too.
E-mail: tsiegfried@nasw.org
