Intrinsic Universality of the aTAM

Intrinsic Universality

An intrinsically universal (IU) model is one which contains some system U, such that for any arbitrary system T within that model, U can be given a starting condition based on T such that U will then completely simulate the behavior of T. That is, U will mimic all behaviors of T, but at a re-scaling in which each n × n block within U, for some \(n \in \mathbb{N}\), can be mapped to a single element of T. Cellular automata and Turing machines are both examples of models which are intrinsically universal.

The aTAM is IU

While an aTAM system can be designed to simulate an arbitrary Turing machine, which could computationally simulate an arbitrary aTAM system, another interesting question was whether or not the aTAM is intrinsically universal, or: Is there a single tile set which can be used to simulate the behavior of any arbitrary aTAM system? Essentially, if the tiles of this "universal" tile set could be arranged to form a seed structure such that that structure contains an encoding of some other aTAM system, say \(\mathcal{T}\), could additional copies of tiles from the universal tile set attach to grow into an assembly which simulates the system \(\mathcal{T}\)? Of course, the simulation would be a scaled up version of the original system, but it must be the case that every behavior that \(\mathcal{T}\) is capable of, the simulating system is also capable of. Preliminary work by Doty, Lutz, Patitz, Summers, and Woods in showed that for a constrained set of aTAM systems, namely those in which all tiles bind with exactly strength \(\tau\) and there are no glue mismatches between adjacent tile edges, that class is intrinsically universal. Furthermore, it was later shown by Doty, Lutz, Patitz, Schweller, Summers, and Woods in that the entire, unconstrained class of aTAM systems is intrinsically universal. In fact, they demonstrated a tile set U and a method for using the definition of an arbitrary aTAM system \(\mathcal{T}\) of any temperature to form a seed structure for U so that the system with that seed, the tiles from U, and at temperature 2, can simulate \(\mathcal{T}\). Thus, a single tile set in a properly seeded system at temperature 2 can simulate the behavior of any aTAM system at any temperature.

IU vs. temperature

The previous result shows a powerful symmetry to the aTAM, since there is a system within it that can behave exactly like any other system within it. In , Meunier, Patitz, Summers, Theyssier, Winslow, and Woods showed that the temperature 2 parameter for systems using the intrinsically universal tile set is in fact a lower bound. They showed that no aTAM tile set exists which can simulate arbitrary aTAM systems of temperature >1, while operating in a system of temperature 1, proving that the cooperative behavior provided by temperature 2 self-assembly can not be simulated at temperature 1. Further, their impossibility result extends to 3D, showing that even 3D temperature 1 aTAM systems cannot simulate 2D temperature 2 aTAM systems, which is contrasted with the facts that 3D temperature 1 systems are capable of universal computation (see The influence of temperature), and the second result of shows that 3D temperature 1 systems can simulate arbitrary 2D temperature 1 systems. These results especially emphasize the fact that the power to perform universal computation does not imply the power to simulate arbitrary behaviors of algorithmic self-assembly.

Answering more of the questions about the limitations of simulation at temperature 1, in Meunier and Woods proved that the class of temperature 1 aTAM systems are not themselves IU. This work also showed that they are not capable of simulating bounded Turing machines, further showing their limitations in terms of computing.

Directedness and IU

A directed system