Difference between revisions of "Self-Assembly of Decidable Sets"
Jump to navigation
Jump to search
| Line 9: | Line 9: | ||
geometrical constraints. | geometrical constraints. | ||
|authors=Matthew J. Patitz and Scott M. Summers | |authors=Matthew J. Patitz and Scott M. Summers | ||
| − | |file=SADS.pdf | + | |file=[[media:SADS.pdf]] |
}} | }} | ||
Revision as of 13:34, 4 December 2011
Published on:
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
