guarantee no glue mismatches, showing that Ω(n) tile types are required to
assemble shapes of diameter n.
However, with slight changes to
the model, universal computation
becomes possible. Adleman et al. 4 devised a nondeterministic temperature
1 tile system that simulates a Turing
machine in the following sense: the
system has many terminal assemblies,
but the unique largest terminal assembly represents the computation. Cook,
Fu, and Schweller18 showed that deterministic tile systems can achieve universal computation if allowed to grow
in three dimensions. Patitz, Schweller,
and Summers41 showed that if negative glue strengths are allowed then
universal computation is possible, essentially using negative-strength glues
to enforce cooperative binding.
But the original question stands:
what is the computational power of deterministic, planar, positive-strength,
temperature 1 self-assembly? Is cooperative binding truly necessary to compute by planar self-assembly?
In the early history of computability
theory, the optimistic term “
elementary” was applied to problems computable in time bounded by a tower
of exponentials such as 222n. It was not
until the 1960s, once faster and faster
computers had been built to execute
actual algorithms, that polynomial
time came to be seen as a more realistic notion of feasibly implementable.
Today we confront a similar situation
in algorithmic self-assembly, where
experimental work has not yet caught
up to theory. When it does, the theory
will doubtlessly take unanticipated
turns. One concrete way that theory
can help experiment today is to further develop error correction, such
as reducing tile complexity of error-correction constructions or handling
broader classes of tile systems than
The complexity of today’s operating systems and other software is
made possible only by the development of software engineering techniques to help manage the complexity. Eventually molecular self-assembly
systems will scale to the point that no
one person could manually keep track
of all the types of molecular compo-
scale to the point
that no one person
keep track of all
the types of
and how they are
to fit together.
nents and how they are all supposed
to fit together. Software simulators for
the a TAM exist40, 55 but require the user
to think at the level of individual tile
types, which quickly begins to feel like
assembly code programming with a
nightmarish instruction set. There is
some preliminary work8, 25 developing
higher-level languages for describing
a TAM tile systems, but we are far from
having a “Python of self-assembly.”
DNA tile assembly is an example
of passive self-assembly, in which the
tiles are mobile but otherwise state-
less. Active self-assembly, using com-
ponents with a changeable state, may
enable sophisticated structures to be
built at a lower cost in terms of time,
tile complexity, or error-resistance.
Majumder, LaBean, and Reif, 36 as well
as Fujibayashi et al., 29 and Padilla,
Liu, and Seeman, 39 have proposed
theoretical suggestions to augment
tiles with a physical mechanism
known as strand displacement to en-
able active signaling across tiles. It
remains to see what will actually work
in the laboratory, but whatever works
will provide a rich theory to explore.
As in any nascent field, the most ex-
citing aspect is not knowing what the
I thank Damien Woods, Matt Patitz, and
Scott Summers for helpful suggestions.
The author was supported by a
Computing Innovation Fellowship under NSF grant 1019343 and NSF grants
CCF-1219274 and CCF-1162589, and
by the Molecular Programming Project
under NSF grant 0832824.
1. Adleman, L.m. molecular computation of solutions to
combinatorial problems. Science 266, 5187 (1994), 1021.
2. Adleman, L.m., Cheng, q., goel, A. and Huang, m-d.
Running time and program size for self-assembled
squares. In Proceedings of STOC (2001), 40–748.
3. Adleman, L.m., Cheng, q., goel, A. and Huang, m-d.,
Kempe, d., de Espanés, P.m. and Rothemund, P. W.K.
Combinatorial optimization problems in self-assembly.
In Proceedings of STOC (2002), 23–32.
4. Adleman, L.m, Kari, J., Kari, L., Reishus, d. and Sosík,
P. The undecidability of the infinite ribbon problem:
Implications for computing by self-assembly. SIAM
Journal on Computing 38, 6 (2009), 2356–2381.
Preliminary version appeared in FOCS 2002.
5. Aggar wal, g. Cheng, q., goldwasser, m.H., Kao, m-Y.,
de Espanés, P.m. and Schweller, R. T. Complexities for
generalized models of self-assembly. SIAM Journal
on Computing 34 (2005), 1493–1515. Preliminary
version appeared in In Proceedings of SODA 2004.
6. Barish, R.d., Rothemund, P. W.K. and Winfree, E.
Two computational primitives for algorithmic self-assembly: Copying and counting. Nano Letters 5
7. Barish, R.d, Schulman, R., Rothemund, P. W.K. and
Winfree, E. An information-bearing seed for nucleating