diagram of laser illumining plate http://people.csail.mit.edu/jaffer/Cell

Nano-Cellular Automata

nanoscale wires  The Incredible Shrinking Circuit (PDF) 
 by Charles M. Lieber  Scientific American 2001-09 
tesselated triangular array  Computation universal 2D Triangular Reversible Partitioned Cellular Automata 
 by Katsunobu Imai and Kenichi Morita 
triangular cellular array 4-Neighbor 3-State Universal Cellular Automaton
hexagonal cellular array  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

Although nearly all signaling in modern computers is binary, three-level logic signaling is possible in CMOS semiconductor circuits. Thus only two 3-state conductors (in and out) would be required between each pair of neighboring cells; a total of 6 connections per cell. This is a significant reduction from the 16 connections required for each cell in Conway's Game of Life and most other two-dimensional cellular automatons being investigated.

Clocks and Power

The automaton requires simultaneous state transitions between neighboring cells. Integrated clock distribution networks become more difficult and consume more "real estate" and power as the density of integrated circuits increase. Traditional clock distribution would limit the quest for the smallest possible cell.

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.

circular waves impinging on plate 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.


The cell can probably be designed so that some sequence of illumination will bring up all the cells in the quiescent state. A precisely steerable electron beam could then set individual cells to other states, embedding a computer design into the array.

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

Even better would be a cellular automaton which can configure its own logic and wiring. Together with an algorithm to construct gates and wires while quarantining defective cells, this is a formula for scalable, flexible computing in the nano-scale future.

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.


Cellular automata made of zero-power (reversible) logic and optically driven constitute a nano-scalable technology which promises exceptional speed of computation. They also require a fresh mindset toward computer engineering. Because cellular propagation takes much longer than electrical propagation, long delay lines are the most space-efficient means of storage in few-state, clocked automatons. Transport of signals should be minimized. Data should flow through processing in the array. Bit-parallel is bad; bit-serial machines in parallel are good.

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.
agj @ alum.mit.edu
Go Figure!