54 citations · 119 across the 20 of their papers we have counts for
25 papers
Hardness of busy beaver value BB(15)
Tristan Stérin, Damien Woods
The busy beaver value BB(n) is the maximum number of steps made by any n-state, 2-symbol deterministic halting Turing machine starting on blank tape. The busy beaver function $n \m…
Small tile sets that compute while solving mazes
Matthew Cook, Tristan Stérin, Damien Woods
We ask the question of how small a self-assembling set of tiles can be yet have interesting computational behaviour. We study this question in a model where supporting walls are pr…
Turning Machines: a simple algorithmic model for molecular robotics
Irina Kostitsyna, Cai Wood, Damien Woods
Molecular robotics is challenging, so it seems best to keep it simple. We consider an abstract molecular robotics model based on simple folding instructions that execute asynchrono…
The Collatz process embeds a base conversion algorithm
Tristan Stérin, Damien Woods
The Collatz process is defined on natural numbers by iterating the map when is even and when is odd. In an effort…
Limitations on counting in Boolean circuits and self-assembly
Tristan Stérin, Damien Woods
In self-assembly, a -counter is a tile set that grows a horizontal ruler from left to right, containing columns each of which encodes a distinct binary string. Counters have…
The program-size complexity of self-assembled paths
Pierre-Étienne Meunier, Damien Regnault, Damien Woods
We prove a Pumping Lemma for the noncooperative abstract Tile Assembly Model, a model central to the theory of algorithmic self-assembly since the beginning of the field. This theo…