Self Assembly and Tiling Theory
By: Noor Sheikh
Overview
Self-assembly is the idea that self-assembling molecules and nanoparticles can do specific and controlled computations because of their naturally driven interactions. This has long been of interest to computer scientists, as the idea of protein-based self-assembling code is quite enticing. The first instance of the field was found when L.M Alderman published a proof of concept, where different molecules of DNA were manipulated into performing the hamiltonian path problem, proving the feasibility of molecular computation.¹
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
The algorithmic way of describing this behavior is with tiling. Tiles are geometric shapes where each side of the shape has a particular ‘stickiness’ referred to as glue. Depending on the problem, the side’s glue can be algorithmically calculated or given. A common model of tiling is called the abstract Tile Assembly Model (aTAM). It was invented by E.Winfree in their thesis in 1998.²
‘Can aTAM Cover an Infinite Plane’ is Turing Reducible to HALT
Tiling as a language is bound by several conditions for the sake of simplicity. These conditions include that there’s a finite set of tiles, each tile has a set of sides, only like sides attach, and all accepted languages can tile infinite square planes. The language of tiling reduces to the language HALT. More interestingly, this proof illustrates how any Turing machine can be made into a set of tiles that computes the same thing. The proof below has been modified for the sake of simplicity and was adapted from Dr. Howard Straubing at Boston College.³
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
The tiles necessary to imitate a Turing machine are as follows:
- Blank tiles: Tiles with a B for Blank on three sides. The + indicates that we’re at the bottom row of the tiling.
- Tape Alphabet Tiles: Tiles for every character ‘g’ in the tape alphabet of the Turing Machine.
- 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.
- 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 tiling begins with the designated start tile designated above. This start tile can only attach across with blank tiles, as shown below
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
As shown above, tiling, and by extension self-assembly, could theoretically imitate any Turing Machine, but there are limits, both in the theory and application. For one thing, despite much research to the contrary, tiling and self-assembly are unable to solve NP-Hard problems in P time. The theoretical solution “in a test tube of DNA” still involves going through every non-deterministic path until completion, presenting the same timing and resource problems as traditional computing. ⁴
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
A fascinating example of using self-assembly is in the new mRNA vaccines used against COVID-19.⁵ Researchers were able to leverage existing self-assembling vaccines, as well as some higher-level biological procedures in order to come up with a Sars-Cov-2 vaccine in record time. Self-assembly techniques are used to first manufacture the vaccine, and then again by body systems to gain immunity. The computing equivalent would be putting some syntax into a computing environment and changing the environment until it made snippets of code. Then the snippets of code would be injected into a computer and self-assemble into copycat malicious software in the computer’s environment. The computer would then not only recognize the no longer benign-looking snippets as an attack but also create a counter security plan against similar software attacks. This showcases the utility of self-assembly in computing and biological space.
References
¹Adleman, L.M. Molecular computation of solutions to combinatorial problems. Science 266, 5187 (1994), 1021.
²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.