  We prove 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 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. In this work, we prove that only very simple shapes can
indeed be programmed, whereas 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.
