Performance limits on chemical computation

A class of novel computers uses solute concentrations of distinct chemical species as logic signals and diffusion for signal transport. I establish a bound on the speed, density, and error rate of such computers from first principles. I let the chemical computer engineer choose a "design tuple" of independent parameters: number of chemical species, total solute concentration, signal molecule size, and a parameter called the "cell size". I establish a functional relation between the design tuple, and the "performance tuple": (operating frequency, signal density, error rate). I give a lower bound on the probability of a logic error in one computation step, and an upper bound on the frequency of operation, both as functions of the design tuple. I evaluate these bounds for ssDNA oligomers, and conclude that DNA computation has unacceptable error rates if the hybridization regions are less than eight nucleotides in length. I then argue that, given a suitable scalar-valued performance metric as a function over performance tuples, there is a globally optimal design tuple maximizing performance. I present two conjectures seeking to explain (a) why neurons use small molecules to transport information, and (b) why cells have the size they do. In part two I develop such a performance metric based on Toffoli's computation capacity and computation density, extending and generalizing in these ways: * as a local statistic on a uniform system, it can be evaluated for very large systems without exhaustive counting

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2004

Author dc:creator

• Homsy, George E. (George Edward), 1965-

Advisor dc:contributor.advisor

• Thomas F. Knight.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/30085

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/30085