Difference between revisions of "Self-Assembly of Decidable Sets"
Jump to navigation
Jump to search
m |
|||
| (2 intermediate revisions by 2 users not shown) | |||
| 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 | + | |date=2011/06/01 |
| + | |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
