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\).