  We prove a result which strongly hints at the computational weakness of a
model of tile assembly that has so far resisted many attempts of formal
analysis or positive constructions. Specifically, we prove that, in Winfree's
abstract Tile Assembly Model, when restricted to use only noncooperative
bindings, any long enough path starting from the seed that can grow in all
terminal assemblies is pumpable, meaning that this path can be extended into an
infinite, ultimately periodic path. This result can be seen as a geometric
generalization of the pumping lemma of finite state automata, and closes the
question of what can be computed deterministically in this model. Moreover,
this question has motivated the development of a new method called visible
glues. We believe that this method can also be used to tackle other
long-standing problems in computational geometry, in relation for instance with
self-avoiding paths. Tile assembly (including non-cooperative tile assembly)
was originally introduced by Winfree and Rothemund in STOC 2000 to understand
how to program shapes. The non-cooperative variant, also known as temperature 1
tile assembly, is the model where tiles are allowed to bind as soon as they
match on one side, whereas in cooperative tile assembly, some tiles need to
match on several sides in order to bind. Previously, exactly one known result
(SODA 2014) showed a restriction on the assemblies general non-cooperative
self-assembly could achieve, without any implication on its computational
expressiveness. With non-square tiles (like polyominos, SODA 2015), other
recent works have shown that the model quickly becomes computationally
powerful.
