The Undecidability of the Infinite Ribbon Problem: Implications for Computing by Self-Assembly

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

zbMATH Keywords

undecidability; tiling; DNA computing; molecular computing; self-assembly

Mathematics Subject Classification ID

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, 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