Building finite shapes in the aTAM

Building finite shapes

In order to build any given finite shape, it is trivial to define a tile assembly system which will self-assemble it: simply create a unique tile type for every point in the shape so that the glue between each tile and each neighbor is unique to that pair in that location. Obviously, however, this is the worst possible construction in terms of tile type complexity. Soloveichik and Wifree, in , showed that as long as the shape can be scaled up (meaning that every point in the original shape is replaced by a square block of tiles of some fixed dimension) the tile type complexity for a finite shape \(S\) is bounded above and below by the Kolmogorov complexity of the shape. The Kolmogorov complexity of \(S\), denoted \(K(S)\), is the length in bits of the shortest program which, when run by a universal Turing machine, outputs exactly the points of \(S\) and then halts. They showed that the tile complexity of \(S\) is \(\Theta\left(\frac{K(S)}{\log K(S)}\right)\) by showing that the lower bound holds because otherwise it would contradict the Kolmogorov complexity of the shape, and for the upper bound they provided a construction in which a Turing machine is simulated inside of each scaled up block to read a compressed definition of \(S\) and determine which neighboring locations should have blocks filled in and then passing the program into those blocks and simulating the Turing machine within them, etc. Therefore, the scaling factor \(c\) is proportional to the running time of the Turing machine (and thus can be very large), and the tile complexity arises from the compressed definition of \(S\).

Another interesting aspect to the tile complexity of finite shapes was demonstrated by Bryans, Chiniforooshan, Doty, Kari, and Seki in where they showed that there exist finite shapes which can self-assemble more tile type efficiently by nondeterministic systems than by deterministic, or directed, systems. Both types of systems always create the exact same shape, but where a directed system does so by ensuring that no matter which assembly sequence is followed, a given location always receives a tile of the same type, a nondeterministic system may allow tiles of differing types to occupy a particular position based on the assembly sequence followed. They also showed that the problem of determining the minimum number of tile types which are required to uniquely assemble a given finite shape, if the system isn't constrained to being directed, is complete for the complexity class \(\Sigma^P_2 = NP^{NP}\), while it was shown by Adleman, Cheng, Goel, Huang, Kempe, Moisset de Espanés, and Rothemund in to be NP-complete for directed systems. These results suggest that such nondeterminism adds power and complexity to the aTAM.