http://people.csail.mit.edu/jaffer/Cell
	Nano-Cellular Automata

The Incredible Shrinking Circuit (PDF)   by Charles M. Lieber  Scientific American 2001-09

Computation universal 2D Triangular Reversible Partitioned Cellular Automata   by Katsunobu Imai and Kenichi Morita

4-Neighbor 3-State Universal Cellular Automaton

Universal cellular automaton over a hexagonal tiling with 3 states   by A. Gajardo and E. Goles   International Journal of Algebra and Computation 2001-06

Reading Charles M. Lieber's, The Incredible Shrinking Circuit, Scientific American 2001-09, 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 2-dimensional 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 (non-self) neighbors is three. I created a triangular 4-Neighbor 3-State 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.

The Cell Design

Clocks and Power

Power distribution is less vexing than clock distribution, but must be solved nonetheless. In zero-power CMOS there is no power distribution, only a clock. In order to be a true zero-power design, it must be reversible. In their paper A computation-universal two-dimensional 8-state 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 zero-power. Transmission along wires, also used for storage, is reversible; as are exclusive-or gates. Part of the design rules for nano-circuitry 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.

Configuring

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.

Universal Constructor

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 "non-conductive" area because the neighborhood connectivity of each cell is too limited.

More promising is the idea of etching out regions of non-conductive area from an initial sea of conductive states. But this also seems very difficult using only 3 states.

Conclusion

We have come full circle -- this regime is reminiscent of the drum computers from the dawn of electronic computing.