Nondeterminism

Overview

Nondeterminism in a tile assembly system is when there are points in the assembly sequence when the next time step can be one of multiple different tile attachments. Nondeterminism is important and is required in some instance to achieve certain properties. Hendricks, Patitz, and Rogers proved that the intrinsic universality principle of the abstract Tile Assembly Model relies on nondeterminism, since a deterministic simulator is incapable of universally simulating all other deterministic systems.

Growth Frontier

The first type of nondeterminism occurs whenever there are multiple potential tile attachments in the growth frontier at a certain time step in the assembly sequence. This form of nondeterminism still allows an assembly to be directed, since, even though decisions must be made during the assembly process, all assembly sequences can still lead to the same terminal assembly.

Multiple Tiles with the Same Glues

The next type of nondeterminism is whenever there is a location in the growth frontier that two tiles can attach to. Because making this decision prevents another tile that could have attached from attaching to the assembly in that spot, this nondeterminism doesn't allow for directed systems in the aTAM. However, in models that allow for tiles to break off after they attach, systems with this property can still be directed.

Competition Among Paths

The final form of nondeterminism is whenever separate pieces of the assembly are converging and competing for some overlapping potential tile placements. In the same sense as the last form of nondeterminism, this type also doesn't allow for directed systems unless also allowing for tiles to break off the assembly after they've been attached.