http://people.csail.mit.edu/jaffer/Cell  
NanoCellular Automata 
 
 
 

Reading Charles M. Lieber's, The Incredible Shrinking Circuit, Scientific American 200109, it appears that a uniform cellular automaton array into which an universal Turing machine can be programmed would find application in nanoscale computing.
But practical problems abound. Paramount is that the cell be as simple as possible; perhaps a single molecule crystallized onto a substrate, avoiding lithography altogether.
Among 2dimensional cellular automatons so far investigated, many have the absolute minimum number of states  two. But the number of neighbors is commonly 8 or 9 (a cell depending on its previous state is its own neighbor).
The minimum number of neighbors is two, but the cellular array is then effectively one dimensional, as its cells are strung in long chains. The next smallest number of (nonself) neighbors is three. I created a triangular 4Neighbor 3State Universal Cellular Automaton for Prof. Fredkin's 1974 cellular automata class at MIT; and it is the basis for this exploration.
By setting cells to appropriate states, wiring and logic gates can be configured in this cellular automaton. Given a large enough array, computers can be created within it.
Power distribution is less vexing than clock distribution, but must be solved nonetheless. In zeropower CMOS there is no power distribution, only a clock. In order to be a true zeropower design, it must be reversible. In their paper A computationuniversal twodimensional 8state triangular reversible cellular automaton, Katsunobu Imai and Kenichi Morita put the minimum number of states at 8 for triangular, reversible cellular automata.
A short review of nanoelectronic architectures by M. Forshaw1, R. Stadler, D. Crawley and K. Nikoli calculates severe power dissipation limits for conventional logic gates at nanometer scales. But the bulk of a computer constructed with my cellular automaton can be zeropower. Transmission along wires, also used for storage, is reversible; as are exclusiveor gates. Part of the design rules for nanocircuitry will be minimum spacing between dissipating elements. Even without full reversibility, distributing power through the clock solves many problems.
In a cellular design, no electrical signal on the array travels
further than twice the cell diameter. This limits the minimum clock
period to be greater than the time it takes for electrical signals to
cross 2 cells. For nanometer geometries this excitation can be
optical. A monochromatic, coherent light source (laser) and optics
can be designed so that wavefronts of the clock radiation are parallel
to the substrate. With the substrate part of the laser's resonant
cavity, most of the clock energy can be recovered. The top conductive
layer of each cell is its antenna receiving the clock signal. A
300.nm cell diameter would work with infrared illumination; perhaps
clocking at a blazing 100.THz.
More practical would to create arrays having only the cells intended to hold wires (state 4). The other cell spaces would act as constant sources of state 0.
Input and output signals to and from the array could be through nanowires to cells near the edge of the array.
Logic and wires can be embedded in my automaton, but not constructed. With rules that support signal propagation along wires, wires cannot be grown in a "nonconductive" area because the neighborhood connectivity of each cell is too limited.
More promising is the idea of etching out regions of nonconductive area from an initial sea of conductive states. But this also seems very difficult using only 3 states.
We have come full circle  this regime is reminiscent of the drum computers from the dawn of electronic computing.
Copyright © 2002, 2004, 2007 Aubrey Jaffer
I am a guest and not a member of the MIT Computer Science and Artificial Intelligence Laboratory.
My actions and comments do not reflect in any way on MIT.  
Invention  
agj @ alum.mit.edu  Go Figure! 