IU Results in Diffusion-Restricted and Directed aTAMs

Definition of "Diffusion Restricted"

An \(n\)-dimensional aTAM is diffusion-restricted if and only if the paths along which attaching tiles diffuse in a TAS it models are confined to the \(n\)-plane containing its assembly.

Planar and Spatial aTAMs

We call the diffusion-restricted 2D aTAM "planar" because its diffusion-paths are embedded in the plane. Let \(T\) be a TAS modeled by the planar aTAM. Suppose over the course of its growth \(\mathcal{T}\)'s assembly comes to enclose a tileless region. From the time of enclosure onward it will be impossible for a tile to attach within the enclosed region, as the confinement of its path of diffusion to the plane would force it to move from the outside of the assembly through a wall of existing tiles, which is impossible.

Contrast this to the regular 2D aTAM wherein tiles are permitted to attach within an enclosed region by diffusing into it from the third dimension along an axis orthogonal to the plane.

The 3D diffusion-restricted TAS, or "spatial TAS", prohbits attachment within enclosed volumes, while the regular 3D TAS permits it via the fourth dimension.

Without added constraint the general 1D aTAM is diffusion-restricted. This is because the 1D aTAM cannot enclose a nonzero length, as doing so would require there to be tiles on either side of the enclosed space, and one side could only have been reached from the other by a bridge of tiles filling the gap between.

The 1D (Linear) (Directed) aTAM Is Not IU

Suppose there exists a tileset \(U\) which can intrinsically simulate all TASs in the 1D aTAM. Let \(|U| = n\). We can define a TAS \(X\) which assembles a line of length \(n+1\). \(U\) cannot simulate \(X\), as it must either assemble a line of \(n\) or fewer tiles or assemble a line of infinite length by the pumping lemma. \(X\) is both directed and linear. This shows that none of the general 1D aTAM, the linear 1D aTAM, the directed 1D aTAM and the linear directed 1D aTAM possess an intrinsically-universal tileset.

The Planar aTAM Is Not IU

For any candidate TAS \(U\), one can construct a TAS \(X\) which \(U\) cannot simulate within the planar aTAM model. \(X\) encloses a region \(A\) of the plane in such a way that while simulating \(X\) \(U\) must either:

1. Fail to enclose \(A\)'s image \(A'\) in the simulation, and as such permit growth within \(A'\) when it is prohibited within \(A\) by \(X\).

2. Or place a tile in a location which should remain empty.

Hence, there exists no TAS \(U\) which can intrinsically simulate all TASs within the planar aTAM model.

The Directed Planar aTAM Is Not IU

For any directed candidate \(U\), one can construct a directed TAS \(T\) which \(U\) cannot simulate within the planar aTAM model. \(U\) must allow for multiple terminal assemblies in simulating \(T\), a violation of \(T\)'s directedness.

The 3D aTAM is IU

A certain tileset \(U\) may be shown to be intrinsically universal within the 3D aTAM model by showing that it may be used to construct four modules which when connected to one another simulate the action of a single tile in an arbitrary TAS \(T\). These modules are:

1. The genome, which encodes the production rules of the tile system simulated and the four modules;

2. The adder array, which determines whether there is sufficient binding strength from the glues surrounding the cell to permit an attachment;

3. The bracket, which determines into which macrotile the cell may resolve and selects one;

4. The external communication, which communicates the bracket's decision to surrounding cells.

The Directed 3D aTAM is IU

The simulation scheme given to show that the general 3D aTAM is intrinsically universal has the property that when simulating directed systems it is itself directed. Hence, the directed 3D aTAM is IU.

The Spatial aTAM is IU

It is possible to augment the above scheme in such a way as not to permit tile additions within closed volumes. Hence, the spatial aTAM is IU.

The full details of the above constructions are given by the below paper.

References

The Impacts of Dimensionality, Diffusion, and Directedness on Intrinsic Universality in the abstract Tile Assembly Model(full version or arxiv), Daniel Hader, Aaron Koch, Matthew J. Patitz, and Michael Sharp. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms 2020 (SODA '20), (January 5-8, 2020, Salt Lake City, UT), pp. 2607-2624.