Difference between revisions of "Self-Assembly of Decidable Sets"
Jump to navigation
Jump to search
Wiki admin (talk | contribs) |
m |
||
| Line 10: | Line 10: | ||
|authors=Matthew J. Patitz and Scott M. Summers | |authors=Matthew J. Patitz and Scott M. Summers | ||
|date=2011/06/01 | |date=2011/06/01 | ||
| − | |file=[[media:SADS.pdf]] | + | |file=[[media:SADS.pdf | Self-Assembly of Decidable Sets.pdf]] |
}} | }} | ||
Latest revision as of 11:46, 22 June 2021
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
