Difference between revisions of "Self-Assembly of Decidable Sets"
Jump to navigation
Jump to search
Wiki admin (talk | contribs) |
|||
| Line 9: | Line 9: | ||
geometrical constraints. | geometrical constraints. | ||
|authors=Matthew J. Patitz and Scott M. Summers | |authors=Matthew J. Patitz and Scott M. Summers | ||
| + | |date=2011/06/01 | ||
|file=[[media:SADS.pdf]] | |file=[[media:SADS.pdf]] | ||
}} | }} | ||
Revision as of 14:10, 23 January 2012
Published on: 2011/06/01
Abstract
The theme of this paper is computation in Winfree’s Abstract Tile Assembly Model (TAM). We first review a simple, well-known tile assembly system (the “wedge construction”) that is capable of universal computation. We then extend the wedge construction to prove the following result: if a set of natural numbers is decidable, then it and its complement’s canonical two-dimensional representation self-assemble. This leads to a novel characterization of decidable sets of natural numbers in terms of self-assembly. Finally, we show that our characterization is robust with respect to various (restrictive) geometrical constraints.
Authors
Matthew J. Patitz and Scott M. Summers
