The Undecidability of the Infinite Ribbon Problem: Implications for Computing by Self-Assembly
From MaRDI portal
Publication:3654379
DOI10.1137/080723971zbMath1191.68419OpenAlexW2062970222WikidataQ59884888 ScholiaQ59884888MaRDI QIDQ3654379
Dustin Reishus, Lila Kari, Petr Sosík, Jarkko Kari, Leonard M. Adleman
Publication date: 6 January 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/080723971
Undecidability and degrees of sets of sentences (03D35) Cellular automata (computational aspects) (68Q80) Dynamical aspects of cellular automata (37B15) General biology and biomathematics (92B05)
Related Items (13)
Arithmetic computation in the tile assembly model: addition and multiplication ⋮ Limitations of self-assembly at temperature 1 ⋮ Polyominoes simulating arbitrary-neighborhood zippers and tilings ⋮ Nondeterministic polynomial time factoring in the tile assembly model ⋮ Solving NP-complete problems in the tile assembly model ⋮ Plane-Filling Properties of Directed Figures ⋮ Snakes and Cellular Automata: Reductions and Inseparability Results ⋮ On the effects of hierarchical self-assembly for reducing program-size complexity ⋮ Towards a neighborhood simplification of tile systems: from Moore to quasi-linear dependencies ⋮ Self-assembly of decidable sets ⋮ Strict self-assembly of discrete Sierpinski triangles ⋮ Path finding in the tile assembly model ⋮ Exact Shapes and Turing Universality at Temperature 1 with a Single Negative Glue
This page was built for publication: The Undecidability of the Infinite Ribbon Problem: Implications for Computing by Self-Assembly
