We consider a solution of automata similar to Population Protocols and Network Constructors. The automata (or nodes) move passively in a well-mixed solution and can cooperate by interacting in pairs. Every such interaction may result in an update of the local states of the nodes. Additionally, the nodes may also choose to connect to each other in order to start forming some required structure. We may think of such nodes as the smallest possible programmable pieces of matter. The model that we introduce here is a more applied version of Network Constructors, imposing physical (or geometrical) constraints on the connections. Each node can connect to other nodes only via a very limited number of local ports, therefore at any given time it has only a bounded number of neighbors. Connections are always made at unit distance and are perpendicular to connections of neighboring ports. We show that this restricted model is still capable of forming very practical 2D or 3D shapes. We provide direct constructors for some basic shape construction problems. We then develop new techniques for determining the constructive capabilities of our model. One of the main novelties of our approach, concerns our attempt to overcome the inability of such systems to detect termination. In particular, we exploit the assumptions that the system is well-mixed and has a unique leader, in order to give terminating protocols that are correct with high probability (w.h.p.). This allows us to develop terminating subroutines that can be sequentially composed to form larger modular protocols. One of our main results is a terminating protocol counting the size @math of the system w.h.p.. We then use this protocol as a subroutine in order to develop our universal constructors, establishing that the nodes can self-organize w.h.p. into arbitrarily complex shapes while still detecting termination of the construction.
Nature has an intrinsic ability to form complex structures and networks via a process known as . By self-assembly, small components (like e.g. molecules) automatically assemble into large, and usually complex structures (like e.g. a crystal). There is an abundance of such examples in the physical world. Lipid molecules form a cell's membrane, ribosomal proteins and RNA coalesce into functional ribosomes, and bacteriophage virus proteins self-assemble a capsid that allows the virus to invade bacteria @cite_21 . Mixtures of RNA fragments that self-assemble into self-replicating ribozymes spontaneously form cooperative catalytic cycles and networks. Such cooperative networks grow faster than selfish autocatalytic cycles indicating an intrinsic ability of RNA populations to evolve greater complexity through cooperation @cite_14 . Through billions of years of prebiotic molecular selection and evolution, nature has produced a basic set of molecules. By combining these simple elements, natural processes are capable of fashioning an enormously diverse range of fabrication units, which can further self-organize into refined structures, materials and molecular machines that not only have high precision, flexibility and error-correction capacity, but are also self-sustaining and evolving. In fact, nature shows a strong preference for bottom-up design.
@cite_14 @cite_21
2021492857 2044709436
In models of early life it has been suggested that life and evolution would be more easily achieved if RNA molecules could interact, rather than function independently; here an in vitro system is designed with several RNA fragments that can assemble into a ribozyme, showing that cooperative networks formed by these fragments outcompete self-catalytic RNA fragments. Self-assembly is the process by which small components automatically assemble themselves into large, complex structures. Examples in nature abound: lipids self-assemble a cell's membrane, and bacteriophage virus proteins self-assemble a capsid that allows the virus to invade other bacteria. Even a phenomenon as simple as crystal formation is a process of self-assembly. How could such a process be described as "algorithmic?" The key word in the first sentence is automatically. Algorithms automate a series of simple computational tasks. Algorithmic self-assembly systems automate a series of simple growth tasks, in which the object being grown is simultaneously the machine controlling its own growth.