Self Assembly and Tiling Theory

By: Noor Sheikh

Overview

This idea is seen often in nature, a notable example being in molecules like DNA. It’s also used in fields like nanotechnology and virology; nanomaterials and viral capsids are known to self-assemble.

Tiling

‘Can aTAM Cover an Infinite Plane’ is Turing Reducible to HALT

For the sake of this proof L(tiling) is as illustrated below:

Some rules to follow for this proof include that tiles can not be rotated and only stick in positions where all their edges match. In general, tiles for this proof have state info and read info from the left and right, and tape info at the top and bottom.

Tiles for a Tiling to Mimic a Turing Machine

  • Blank tiles: Tiles with a B for Blank on three sides. The + indicates that we’re at the bottom row of the tiling.
.Blank Tile
  • Tape Alphabet Tiles: Tiles for every character ‘g’ in the tape alphabet of the Turing Machine.
Tape Alphabet Tiles
  • Rule Tiles: These tiles exist for every rule that says ‘at state p, if you read a, go to state q, write b to the tape alphabet, and move right or left on the tape. Special rule tiles are needed with 0’s which simply attach onto the leftmost row of computation. The tiles with the c’s fill in space for each row of computation.
Left: Rule tiles for when the rule moves right on the tape; Right: for when the rule moves left on the tape
  • Start Tile: This tile starts the tiling with a start state of Qo. The two stars indicate the left-hand edge.

Building a Tiling Machine that Mimics the Turing Machine

The blank tiles can go on for infinity, but the only way to move on from the start state is with a rule tile that reads the start state and continues the tiling. Such a tile is shown attached below.

The only tile that can attach adjacently to that is another rule tile from the set, and the rest can only be filled in with more blank tiles, as shown below.

The only way for the tiling to continue from here is if there’s a rule tile that matches reading B at state p, just as the only way for a Turing Machine to continue computing is if there's a rule for when you’re at state P reading B. If such a rule tile exists, the tiling would continue. A tape alphabet tile would fill in the leftmost space and the rule and blank tiles fill in the rest.

Therefore this tiling could only fill an infinite plane if the Turing machine it’s emulating could do the same. Thus, if there existed a decider that could determine whether a Tiling machine could span an infinite plane, you'd be able to decide HALT. This means the language of spanning an infinite square plane is undecidable.

Limits of Tiling and Future Work

Additionally, DNA and natural protein processes can turn in 3D space, as well as make incorrect matches or spontaneously detach, which is a limitation of aTAM. However, a newer tiling system called the kinetic Tile Assembly Model (kTAM) uses more realistic rules. Additionally, efforts have been made for a proofreading scheme to correct incorrect matches, as happens with DNA. ⁴

Future work is also focused on making higher-level self-assembly programs and catching the experimental work up to the current theory.

Self Assembly and COVID-19

References

²Winfree, E. Algorithmic Self-Assembly of DNA. Ph.D. thesis, California Institute of Technology, June 1998.

³Straubing, Howard. “Tiling Problems.” Http://Www.cs.bc.edu/, Computer Science Department St. Mary’s S251 Boston College, www.cs.bc.edu/~straubin/cs385-07/tiling.

⁴Doty, David. “Theory of Algorithmic Self-Assembly.” Communications of the ACM, vol. 55, no. 12, Dec. 2012, pp. 78–88., doi:10.1145/2380656.2380675.

⁵Kim, Jeonghwan, et al. “Self-Assembled MRNA Vaccines.” Advanced Drug Delivery Reviews, vol. 170, 2021, pp. 83–112., doi:10.1016/j.addr.2020.12.014.