Ultimate Theoretical Models
of Nanocomputers

Michael P. Frank* and Thomas F. Knight, Jr.

Massechusetts Institute of Technology AI Lab
545 Technology Square, Room 747
Cambridge MA 02139
telephone: (617) 253-4175
fax: (617) 253-5060
©1997 Michael P. Frank

This is an abstract for a talk to be given at the
Fifth Foresight Conference on Molecular Nanotechnology.
This abstract is also available at

The full paper is available at

The article is partially based on previous work by the author
and co-workers, namely
an existing unpublished memo
and a
draft manuscript submitted to UMC '98.


Although a complete nanotechnology does not yet exist, we can already foresee some new directions in theoretical computer science that will be required to help us design maximally efficient computers using nano-scale components. In particular, we can devise novel theoretical models of computation that are intended to faithfully reflect the computational capabilities of physics at the nano-scale, in order to serve as a basis for the most powerful possible future nanocomputer architectures.

In this paper we present arguments that a reversible 3-D mesh of processors is an optimal physically-realistic model for scalable computers. We show that any physical architecture based on irreversible logic devices would be asymptotically slower than realizations of our model, and we argue that no physical realization of computation aside from quantum computation could be asymptotically faster.

We also calculate, using parameters from a variety of different existing and hypothetical technologies, how large a reversible computer would need to be in order to be faster than an irreversible machine. We find that using current technology, a reversible machine containing only a few hundred layers of circuits could outperform any conventional machine, and that a reversible computer based on nanotechnology would only need to be a few microns across in order to outperform any possible irreversible technology.

We argue that a silicon implementation of the reversible 3-D mesh could be valuable today for speeding up certain scientific and engineering computations, and propose that the model should become a focus of future study in the theory of parallel algorithms for a wide range of problems.

*Corresponding Address:
Massachusetts Institute of Technology, AI Lab, 545 Technology Square, Room 747, Cambridge, MA 02139, ph: 617-253-4175, fax: 617-253-5060, email: mpf@ai.mit.edu