Adding and multiplying in the tile assembly model
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~\cite{}{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.},
}