Power of Self-Assembly at Temperature 1

A paper showing that a temperature 1 deterministic tile assembly system can only assemble semilinear sets, and that no discrete self-similar fractal assembles in a temperature 1, pumpable, directed tile assembly system.

Abstract

We prove that if a set \(X \subseteq Z^2\) weakly self-assembles at temperature 1 in a deterministic (Winfree) tile assembly system satisfying a natural condition known as pumpability, then X is a semilinear set. This shows that only the most simple of infinite shapes and patterns can be constructed using pumpable temperature 1 tile assembly systems, and gives evidence for the thesis that temperature 2 or higher is required to carry out general-purpose computation in a deterministic two-dimensional tile assembly system. We employ this result to show that, unlike the case of temperature 2 self-assembly, no discrete self-similar fractal weakly self-assembles at temperature 1 in a pumpable tile assembly system

Overview

Many proofs in temperature 2 self-assembly rely on the power of cooperation. Temperature 2 self-assembly can use the necessary binding between two tiles to impart information about the geometry of the shape and encode more information than a single glue alone. This paper demonstrates many limitations of temperature 1 self-assembly which lacks cooperation. Using an assumption that the temperature 1 tile system is pumpable, this paper proves that the system can only weakly assemble semilinear sets, i.e. finite unions of linear sets. Semilinear sets have been shown to be logically and computationally very simple by equivalance to and simulation of other basic systems. Arguing that if a tile assembly system can be said to compute that weak self-assembly of a set is a reasonable interpretation of that computation, and thus given the limitation stated above on the weak self-assembly capabilities of temperature 1 pumpable tile system, this paper concludes that directed, pumpable, temperature 1 tile assembly systems are incapable of general-purpose deterministic computation without relaxing the model. It further offers a proof that no discrete self-similar fractal self-assembles in such a system.

Results

The main proof begins by showing that for an arbitrary semilinear set there are two unary languages defined by the projections of the semilinear set onto the x and y axes, and that these unary languages are regular. Having proved that semilinear sets are the computationally simplest sets in \(\mathbf{Z}^2\), the paper moves on to the main proof that all pumpable tile self-assembly systems weakly self-assemble only semilinear sets and that all semilinear sets are weakly self-assembled by such a system.

Intuitively, this proof relies on the fact that the set is either an infinite grid(which is linear by using unit vectors) or the union of finitely many paths and combs. The argument is that since these systems are pumpable, all the finite sets must be within a certain radius of the origin or else they could be pumped to infinity. This radius restricts the possible slopes to a finite number, and thus the set to a finite number of paths and combs. For details, refer to the paper itself .

The second result refers to the impossibility of weakly self-assembling a discrete self-similar fractal in a pumpable temperature 1 tile assembly system. This proof follows directly from the first, main, result and the observation that no semilinear set is a discrete self-similar fractal. Informally, all semilinear sets must either contain a linear set composed of linearly independent vectors, which then has dimension at least 2, or not, which then has dimension at most 1. In either case, it cannot be a fractal which is defined to have dimension between 1 and 2.

Future Work

The most immediate conjecture offered by the authors is the possible removal of the pumpability requirement. The authors also consider the possiblity that the hypothesis of directedness may also be ultimately superfluous. Presuming these conjectures true, this would imply that temperature 1 self-assembly systems are incapable of general purpose deterministic computation.