The influence of temperature

At temperature 2 and above, it is possible to design systems which make use of a feature commonly referred to as cooperation in which the prior placement of two tiles in specific relative positions is required before the attachment of a third tile is possible. This cooperative behavior is what is commonly attributed with providing the aTAM with its ability to perform computations, and disappears at temperature 1 Thus, for aTAM systems whose temperature is 1, it is conjectured that both: 1. Turing universal computation by a deterministic aTAM system is impossible, and 2. any aTAM system which deterministically produces an n × n square requires a minimum of 2n-1 tile types. Partial progress toward the proof of these conjectures was achieved by Doty, Patitz, and Summers in . Maňuch, Stacho, and Stoll also studied a variant of the problem, focusing on finite assemblies in which mismatches are not allowed, and proved that in such cases \(\Omega(n)\) tile types are required to assemble a shape whose diameter is \(n\). Nonetheless, the general problem remains open.

Despite the previous conjectures about the aTAM at temperature \(1\), in it was shown by Cook, Fu, and Schweller that, by slightly relaxing the requirements, Turing universal computation is in fact possible. Namely, if the assembly is allowed to proceed into the third-dimension, utilizing only 2 planes, or if the computation is allowed to prematurely terminate with some arbitrarily low probability, then a universal Turing machine can be simulated at temperature 1. (See Intrinsic universality of the aTAM for related results.)

Moving in the other direction, Chen, Doty, and Seki in showed that there exist tile assembly systems which require temperatures exponential in the number of tile types they contain. They showed that for every n, there exists a tile assembly system with n tile types whose "behavior" cannot be preserved while using a temperature less than \(2^{n/4}\), which means that it is not possible to modify the system to use a lower temperature while ensuring that all tiles are still only able to bind using the same subsets of sides, and produce the same result. For this result they utilize cooperative binding on 3 sides, which they call 3-cooperative, as opposed to the 2-cooperative systems previously discussed. It turns out that while 3-cooperativity results in systems which require temperatures exponential in the number of tile types they contain, 2-cooperative system only require temperatures linear in the number of tile types. (Note that these results are based on the assumption of integer strength glues, which is in fact how the aTAM is defined.) They also gave an algorithm which is able to find the minimal tile system to build an n × n square at any temperature in polynomial time. Further, in , Seki and Okuno show that given a temperature τ > 4 and a shape, it is NP-hard to find the minimum tile assembly system which assembles the shape at or below temperature τ, and that it is also NP-hard to find the optimal (lowest) temperature for a system for which the glue strengths and temperature are not specified, but the cooperative behaviors of the tiles are (i.e. how they can cooperate to form sufficient bonds).