The Impacts of Dimensionality, Diffusion, and Directedness on Intrinsic Universality in the abstract Tile Assembly Model

In this paper we present a series of results related to mathematical models of self-assembling systems of tiles and the impacts that three diverse properties have on their dynamics. In these self-assembling systems, initially unorganized collections of tiles undergo random motion and can bind together, if they collide and enough of their incident glues match, to form assemblies. Here we greatly expand upon a series of prior results which showed that (1) the abstract Tile Assembly Model (aTAM) is intrinsically universal (FOCS 2012), and (2) the class of directed aTAM systems is not intrinsically universal (FOCS 2016). Intrinsic universality (IU) for a model (or class of systems within a model) means that there is a universal tile set which can be used to simulate an arbitrary system within that model (or class). Furthermore, the simulation must not only produce the same resultant structures, it must also maintain the full dynamics of the systems being simulated and display the same behaviors modulo a scale factor. While the FOCS 2012 result showed that the standard, two-dimensional (2D) aTAM is IU, here we show that this is also the case for the three-dimensional (3D) version. Conversely, the FOCS 2016 result showed that the class of aTAM systems which are directed (a.k.a. deterministic, or confluent) is not IU, meaning that there is no universal simulator which can simulate directed aTAM systems while itself always remaining directed, implying that nondeterminism is fundamentally required for such simulations. Here, however, we show that, in 3D, the class of directed aTAM systems is actually IU, i.e. there is a universal directed simulator for them. This implies that the constraint of tiles binding only in the plane forced the necessity of nondeterminism for the simulation of 2D directed systems. This then leads us to continue to explore the impacts of dimensionality and directedness on simulation of tile-based self-assembling systems by considering the influence of more rigid notions of dimensionality. Namely, we introduce the Planar aTAM, where tiles are not only restricted to binding in the plane, but they are also restricted to traveling within the plane, and we prove that the Planar aTAM is not IU, and prove that the class of directed systems within the Planar aTAM also is not IU. Finally, analogous to the Planar aTAM, we introduce the Spatial aTAM, its 3D counterpart, and prove that the Spatial aTAM is IU. This paper adds to a broad set of results which have been used to classify and compare the relative powers of differing models and classes of self-assembling systems, and also helps to further the understanding of the roles of dimension and nondeterminism on the dynamics of self-assembling systems. Furthermore, to prove our positive results we have not only designed, but also implemented what we believe to be the first IU tile set ever implemented and simulated in any tile assembly model, and have made it, along with a simulator which can demonstrate it, freely available.