The Undecidability of the Infinite Ribbon Problem: Implications for Computing by Self-Assembly
From MaRDI portal
Publication:3654379
DOI10.1137/080723971zbMath1191.68419WikidataQ59884888 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
03D35: Undecidability and degrees of sets of sentences
68Q80: Cellular automata (computational aspects)
37B15: Dynamical aspects of cellular automata
92B05: General biology and biomathematics
Related Items
Towards a neighborhood simplification of tile systems: from Moore to quasi-linear dependencies, Self-assembly of decidable sets, Limitations of self-assembly at temperature 1, Polyominoes simulating arbitrary-neighborhood zippers and tilings, Arithmetic computation in the tile assembly model: addition and multiplication, Nondeterministic polynomial time factoring in the tile assembly model, Solving NP-complete problems in the tile assembly model, Strict self-assembly of discrete Sierpinski triangles, Path finding in the tile assembly model, On the effects of hierarchical self-assembly for reducing program-size complexity, Plane-Filling Properties of Directed Figures, Snakes and Cellular Automata: Reductions and Inseparability Results, Exact Shapes and Turing Universality at Temperature 1 with a Single Negative Glue