View source for Performing computations

Early work in DNA computing by Len Adleman <ref name = AdlemanNPProbs /> investigated the feasibility of using custom designed DNA molecules to solve NP-complete problems by performing massively parallel computations.  The general concept is to have huge numbers of individual molecular complexes which nondeterministically each select a potential solution to a given instance of an NP-complete problem and then each perform the necessary computation to determine if the selected solution is correct.  As long as there is a way to easily select the correct answers from the sea of failures, the hope was to provide a method to quickly solve such problems by harnessing the massive numbers of molecules which can compute in parallel.  Adleman was able to solve a version of the Hamiltonian path problem for a graph of 7 vertices, proving the concept.  Since then, a series of results by Brun <ref name=BrunNPProbs />, Cheng et al. <ref name=ChengChHuZhXu10NPProbs />, Cheng and Xiao <ref name=ChengXiaoNPProbs />, and Wang et al. <ref name=WangNPProbs /> have continued to demonstrate the theoretical ability of the aTAM to solve such problems.  Unfortunately, however, as the size of a problem instance approaches useful sizes (e.g. even a few hundred nodes for a graph problem), the exponential number of possible solutions inevitably destroys the utility of this approach, for reasonably-sized inputs requiring the number of assemblies to be at least equivalent to the number of particles in the universe.

While tile-based self-assembly may not be practically useful for solving computationally intractable NP-complete problems, there are still many other interesting problems to ask about its computational power.  While the previously mentioned methods for solving such problems was to use many assemblies in parallel, it is interesting to consider what is possible for any individual assembly in terms of computation.  Since the aTAM has been shown to be computationally universal, a single seeded assembly can simulate an arbitrary Turing machine. However, there are even more complicated computations which can be considered, and in doing so one of the fundamental characteristics of tile-based self-assembly is confronted:  computational space, which is consumed by tiles attaching to an assembly, is analogous to write-once memory.  Once a tile is placed, having performed its part of the computation (by converting the information encoded by its input glues into information encoded by its output glues), it can never change or be removed.  This causes difficulties related to performing computations which are unique to such a physical model, and the following results have helped to uncover the complex ways in which geometry can be related to computation.

In <ref name=jSADS />, Patitz and Summers showed that a set of natural numbers $D \subseteq \mathbb{N}$ is decidable if and only if $D \times \{0\}$ and $D^c \times \{0\}$ weakly self-assemble.  That is, the canonical representations of $D$ and the complement of $D$ weakly self-assemble. For $D \times \{0\}$ to weakly self-assemble, at every point along the $x$-axis such that the value of the $x$ coordinate is contained in $D$, the tile placed at that location is colored black.  All other locations remain either untiled or receive a tile which is not black.  The construction for <ref name=jSADS /> is a relatively straightforward ``stacking'' of Turing machine simulations, so that a given Turing machine $M$ which decides the language in question is first simulated on input $0$, then immediately above that $M(1)$ is simulated, etc.  As each simulation completes, the ``answer'' of whether or not that input is in the language is propagated via a one-tile-wide path down the side of the previous computations to the $x$-axis where the appropriately colored tile attaches.

In <ref name=jCCSA />, Lathrop, Lutz, Patitz, and Summers answered the more complicated question of whether a similar result applied to computably enumerable (a.k.a. recursively enumerable) languages. They showed that a set of natural numbers $D \subseteq \mathbb{N}$ is computably enumerable if and only if the set $X_A = \{(f(n),0) | n \in D \}$ weakly self-assembles (where $f$ is a roughly quadratic function).  For that construction, since any Turing machine $M$ used to determine membership in $D$ cannot be guaranteed to halt for non-members, the simple ``stacking'' construction cannot work.  Instead, the construction performs the infinite series of computations side-by-side, spread out along the $x$-axis (hence the need for $f$), providing a potentially infinite amount of tape space for each computation while ensuring that none of them collide and a path to the relevant point on the $x$-axis always remains available for cases in which a black tile must be placed.  The space reserved for each computation is achieved by a scheme in which each computation proceeds with each row simply copying the row beneath it for most rows, and then with a frequency half that of the computation to its immediate left, a row performs a new step of the computation.  This, combined with a unique and well-defined slope for the assembly representing each computation ensures that the potentially infinite space requirements for every computation can be assured.

On the other hand, showing a limitation to the power of computation by self-assembly in the aTAM, in <ref name=jCCSA /> they showed there there exist decidable sets of pairs of integers, or points (i.e. $D \subseteq \mathbb{Z}^2$), which do not weakly self-assemble in the aTAM.  Their proof leverages the fact that space is not reusable in aTAM assembly, and that new space must therefore constantly be used to perform each subsequent step of a computation.  They designed a pattern consisting of an infinite sequence of concentric diamonds which were centered on the origin and whose diameters were specified by a decidable set of natural numbers.  By employing the time hierarchy theorem <ref name=HS1965 />, they were able to show that there exist sets of diameters whose time complexity is so great (i.e. the amount of time required to computer whether a value is in the set) that if the pattern of diamonds with those diameters could self-assemble it would contradict the time complexity of the set.  Essentially, the computation to determine whether or not the diamond at some particular diameter should be included in the pattern could not be performed by tiles from within that diamond and must therefore use space that may be required to mark subsequent diamonds.  This result shows a limitation to the computational power of the aTAM, and the strong correlation between geometry and computation within it.

==References==
<references>

<ref name =AdlemanNPProbs><bibtex>
@article{AdlemanNPProbs,
 author = {Adleman, Leonard M.},
 title = {Molecular computation of solutions to combinatorial problems},
 journal = {Science},
 issue_date = {Nov. 1994},
 volume = {266},
 number = {11},
 month = nov,
 year = {1994},
 issn = {0036-8075},
 pages = {1021--1024},
 numpages = {4},
 url = {http://dl.acm.org/citation.cfm?id=189441.189442},
 acmid = {189442},
 publisher = {American Association for the Advancement of Science},
 address = {Washington, DC, USA},
}

<ref name =BrunNPProbs><bibtex>
@article{BrunNPProbs,
 author = {Brun, Yuriy},
 title = {Solving NP-complete problems in the tile assembly model},
 journal = {Theor. Comput. Sci.},
 issue_date = {April, 2008},
 volume = {395},
 number = {1},
 month = apr,
 year = {2008},
 issn = {0304-3975},
 pages = {31--46},
 numpages = {16},
 url = {http://dx.doi.org/10.1016/j.tcs.2007.07.052},
 doi = {10.1016/j.tcs.2007.07.052},
 acmid = {1355014},
 publisher = {Elsevier Science Publishers Ltd.},
 address = {Essex, UK},
 keywords = {Crystal-growth, Distributed computing, Molecular computation, NP-complete, Natural computation, Nondeterministic computation, Parallel computing, Self-assembly, SubsetSum, Tile assembly model},
}

<ref name =ChengChHuZhXu10NPProbs><bibtex>
@ARTICLE{ChengChHuZhXu10NPProbs,
  author = {Zhen Cheng and Zhihua Chen and Yufang Huang and Xuncai Zhang and Jin Xu},
  month = {November},
  year = 2010,
  title = {Implementation of the Timetable Problem Using Self-assembly of DNA Tiles},
  journal = {International Journal of Computers, Communications \& Control},
  volume = {V},
  number = 4,
  pages = {490--505}
}

<ref name =ChengXiaoNPProbs><bibtex>
@article {ChengXiaoNPProbs,
	author = "Cheng, Zhen and Xiao, Jianhua",
	title = "Algorithmic Tile Self-Assembly Model for the Minimum Set Cover Problem",
	journal = "Journal of Bionanoscience",
	volume = "6",
	number = "2",
	year = "2012",
	pages = "69-77",
	url = "http://www.ingentaconnect.com/content/asp/jobn/2012/00000006/00000002/art00001",
	doi = "doi:10.1166/jbns.2012.1079"
}

<ref name =WangNPProbs><bibtex>
@article {WangNPProbs,
	author = "Wang, Yanfeng and Lu, Weili and Bai, Xuewen and Wei, Donghui and Cui, Guangzhao",
	title = "DNA Tile Assembly for Degree-Constrained Minimum Spanning Tree",
	journal = "Journal of Bionanoscience",
	volume = "5",
	number = "1",
	year = "2011",
	pages = "41-46",
	url = "http://www.ingentaconnect.com/content/asp/jobn/2011/00000005/00000001/art00005",
	doi = "doi:10.1166/jbns.2011.1050"
}

<ref name =jSADS><bibtex>
@article{jSADS,
  author    = {Patitz, Matthew J. and Summers, Scott M.},
  title     = {Self-assembly of decidable sets},
  journal   = {Natural Computing},
  volume    = {10},
  number    = {2},
  year      = {2011},
  pages     = {853-877},
  ee        = {http://dx.doi.org/10.1007/s11047-010-9218-9},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

<ref name =jCCSA><bibtex>
@article{jCCSA,
  author    = {James I. Lathrop and
               Jack H. Lutz and
               Matthew J. Patitz and
               Scott M. Summers},
  title     = {Computability and Complexity in Self-assembly},
  journal   = {Theory Comput. Syst.},
  volume    = {48},
  number    = {3},
  year      = {2011},
  pages     = {617-647},
  ee        = {http://dx.doi.org/10.1007/s00224-010-9252-0},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

<ref name =HS1965><bibtex>
@article{HS1965,
    author = {Hartmanis, Juris and Stearns, Richard E.},
    citeulike-article-id = {9305320},
    citeulike-linkout-0 = {http://www.jstor.org/stable/1994208},
    journal = {Transactions of the American Mathematical Society},
    month = may,
    pages = {285--306},
    posted-at = {2011-05-17 12:07:55},
    priority = {0},
    title = {{On the Computational Complexity of Algorithms}},
    url = {http://www.jstor.org/stable/1994208},
    volume = {117},
    year = {1965}
}

</references>