  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 theory suggests, and our result proves, that small
differences in the nature of adhesive bindings between abstract square
molecules gives rise to vastly different expressive capabilities.
  In the cooperative abstract Tile Assembly Model, square tiles attach to each
other using multi-sided cooperation of one, two or more sides. This precise
control of tile binding is directly exploited for algorithmic tasks including
growth of specified shapes using very few tile types, as well as simulation of
Turing machines and even self-simulation of self-assembly systems. But are
cooperative bindings required for these computational tasks? The definitionally
simpler noncooperative (or Temperature 1) model has poor control over local
binding events: tiles stick if they bind on at least one side. This has led to
the conjecture that it is impossible for it to exhibit precisely controlled
growth of computationally-defined shapes.
  Here, we prove such an impossibility result. We show that any planar
noncooperative system that attempts to grow large algorithmically-controlled
tile-efficient assemblies must also grow infinite non-algorithmic (pumped)
structures with a simple closed-form description, or else suffer blocking of
intended algorithmic structures. Our result holds for both directed and
nondirected systems, and gives an explicit upper bound of
$(8|T|)^{4|T|+1}(5|\sigma| + 6)$, where $|T|$ is the size of the tileset and
$|\sigma|$ is the size of the seed assembly, beyond which any path of tiles is
pumpable or blockable.
