๐ฎ
๐ฎ
The Ethereal
Deterministic 2-Dimensional Temperature-1 Tile Assembly Systems Cannot Compute
January 24, 2019 ยท The Ethereal ยท ๐ arXiv.org
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Jรฉrรดme Durand-Lose, Hendrik Jan Hoogeboom, Nataลกa Jonoska
arXiv ID
1901.08575
Category
cs.CC: Computational Complexity
Cross-listed
cs.CG,
cs.DS
Citations
2
Venue
arXiv.org
Last Checked
2 months ago
Abstract
We consider non cooperative binding in so called `temperature 1', in deterministic (here called {\it confluent}) tile self-assembly systems (1-TAS) and prove the standing conjecture that such systems do not have universal computational power. We call a TAS whose maximal assemblies contain at least one ultimately periodic assembly path {\it para-periodic}. We observe that a confluent 1-TAS has at most one maximal producible assembly, $ฮฑ_{max}$, that can be considered a union of path assemblies, and we show that such a system is always para-periodic. This result is obtained through a superposition and a combination of two paths that produce a new path with desired properties, a technique that we call \emph{co-grow} of two paths. Moreover we provide a characterization of an $ฮฑ_{max}$ of a confluent 1-TAS as one of two possible cases, so called, a grid or a disjoint union of combs. To a given $ฮฑ_{max}$ we can associate a finite labeled graph, called \emph{quipu}, such that the union of all labels of paths in the quipu equals $ฮฑ_{max}$, therefore giving a finite description for $ฮฑ_{max}$. This finite description implies that $ฮฑ_{max}$ is a union of semi-affine subsets of $\mathbb{Z}^2$ and since such a finite description can be algorithmicly generated from any 1-TAS, 1-TAS cannot have universal computational power.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Computational Complexity
๐ฎ
๐ฎ
The Ethereal
An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
๐ฎ
๐ฎ
The Ethereal
The Parallelism Tradeoff: Limitations of Log-Precision Transformers
๐ฎ
๐ฎ
The Ethereal
The Hardness of Approximation of Euclidean k-means
๐ฎ
๐ฎ
The Ethereal
Slightly Superexponential Parameterized Problems
๐ฎ
๐ฎ
The Ethereal