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 single tile set within it that can be seeded so that it will behave exactly like any other system within it, and in fact this simulated behavior can occur at temperature 2 - regardless of the temperature parameter of the system being simulated. 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. In Hader, Koch, Patitz, and Sharp first proved the the 3D aTAM is IU. They then went on to show that, by careful design of their universal tile set U that U is also an intrinsically universal tile set for the class of directed 3D aTAM systems. This means that U can be used to simulate any directed 3D aTAM system with the simulating system itself remaining directed. This is in contrast with the 2D result of and shows that the necessity for undirectedness in simulation of directed 2D aTAM systems is a product of the planarity of the 2D aTAM.

The tile set which is IU for both the general 3D aTAM as well as the class of directed 3D aTAM systems has been fully implemented (minus a few relatively trivial pieces which don't impact the correctness of its simulation), and can be downloaded from here:

3D aTAM IU tile set and simulation

The above link points to a zip file which contains U (referred to there as Master.tds), a set of Python scripts that can be used to generate U (due to its large size, approximately 152,000 tile types), and a script to generate a seed assembly from a given tile assembly system to be simulated by U.

In order to simulate a 3D aTAM system using U, it is recommended that you use PyTAS. PyTAS has been optimized to work with such a large tile set and the large assemblies required. However, the scale of the simulations is large enough that each supercube representing a single tile of the simulated system requires tens of millions of tiles, and therefore simulation is still very slow and consumes large quantities of memory. In most instances, it is only possible to view the growth of portions of a single supercube.

The AdderArray module

The AdderArray module