Skip to Main content Skip to Navigation
Conference papers

Directed non-cooperative tile assembly is decidable

Abstract : We provide a complete characterisation of all final states of a model called directed non-cooperative tile self-assembly, also called directed temperature 1 tile assembly, which proves that this model cannot possibly perform Turing computation. This model is a deterministic version of the more general undirected model, whose computational power is still open. Our result uses recent results in the domain, and solves a conjecture formalised in 2011. We believe that this is a major step towards understanding the full model. Temperature 1 tile assembly can be seen as a two-dimensional extension of finite automata, where geometry provides a form of memory and synchronisation, yet the full power of these "geometric blockings" was still largely unknown until recently (note that nontrivial algorithms which are able to build larger structures than the naive constructions have been found).
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03362845
Contributor : Frédéric Davesne Connect in order to contact the contributor
Submitted on : Saturday, October 2, 2021 - 2:07:08 PM
Last modification on : Tuesday, October 19, 2021 - 8:12:29 PM

Identifiers

Citation

Pierre-Etienne Meunier, Damien Regnault. Directed non-cooperative tile assembly is decidable. International Conference on DNA Computing and Molecular Programming (DNA 2021), Sep 2021, Oxford, Virtual, United Kingdom. ⟨10.4230/LIPIcs.DNA.27.6⟩. ⟨hal-03362845⟩

Share

Metrics

Record views

45