by Yuriy Brun

Abstract:

The tile assembly model, a formal model of crystal growth, is of special interest to computer scientists and mathematicians because it is universal. Therefore, tile assembly model systems can compute all the functions that computers compute. In this paper, I formally define what it means for a system to compute a function deterministically and present systems that add and multiply. While the proof that the tile assembly model is universal implies the construction of such systems, those systems are in some sense ``large'' and ``slow.'' The systems presented here all use $\Theta(1)$ different tiles (8 to add and 28 to multiply) and compute in time linear in the input size.

Citation:

Yuriy Brun, Adding and multiplying in the tile assembly model, in Proceedings of the 4th Foundations of Nanoscience: Self-Assembled Architectures and Devices (FNANO), 2007.

Related:

Extended and revised in "Arithmetic computation in the tile
assembly model: Addition and multiplication" in Theoretical Computer Science

Bibtex:

@inproceedings{Brun07fnano, author = {Yuriy Brun}, title = {\href{http://people.cs.umass.edu/brun/pubs/pubs/Brun07fnano.pdf}{Adding and multiplying in the tile assembly model}}, booktitle = {Proceedings of the 4th Foundations of Nanoscience: Self-Assembled Architectures and Devices (FNANO)}, venue = {FNANO}, address = {Snowbird, {UT}, {USA}}, month = {April}, date = {18--21}, year = {2007}, note = {Extended and revised in~\ref{Brun07arith}}, previous = {Extended and revised in "Arithmetic computation in the tile assembly model: Addition and multiplication" in Theoretical Computer Science}, abstract = {The tile assembly model, a formal model of crystal growth, is of special interest to computer scientists and mathematicians because it is universal. Therefore, tile assembly model systems can compute all the functions that computers compute. In this paper, I formally define what it means for a system to compute a function deterministically and present systems that add and multiply. While the proof that the tile assembly model is universal implies the construction of such systems, those systems are in some sense ``large'' and ``slow.'' The systems presented here all use $\Theta(1)$ different tiles (8 to add and 28 to multiply) and compute in time linear in the input size.}, }