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 (see Directed Tile Assembly Systems) is one which has a single terminal assembly, meaning that no matter which (valid) assembly sequence it follows it always produces the same assembly with tiles of the exact same types in all of the exact same locations. The aTAM IU construction of , although able to correctly simulate any aTAM system, has the property that even when it is simulating a directed system, the simulator itself is not directed. This is due to so-called ``points of competition where different assembly sequences in which different subassemblies are growing at different relative speeds may reach certain locations first, and depending on which subassembly does so, tiles of different types may be placed there. The question was then: Is this nondeterminism required, or could a directed simulator be built for directed systems?

In , Hendricks, Patitz, and Rogers proved that the nondeterminism in terms of lack of directedness is in fact fundamental. Namely, there exists no IU simulator for the directed class of aTAM systems, meaning that no simulator can always remain directed while simulating directed systems.

3D

Other than the result of which proved that 3D aTAM systems at temperature 1 cannot simulate temperature 2 systems, the previous IU results have dealt with 2D aTAM systems.