3.8 Computation Universal Processors

The preceding sections dealt with specialized processors—the processors designed exclusively to solve some particular problems. One could not use an unmodified reaction-diffusion processor specialized to construct a skeleton to do arithmetical calculations or logical reasoning. Specialization offers relative simplicity in architectural design and efficiency in its functioning, but lacks applicability to all cases. A device is called computation universal if it calculates—at least in posse—any computable logical function. Formally, to prove a physical system's universality, we should demonstrate that a functionally complete logical set (e.g., {NOT, OR}, {NOT, AND}, or Sheffer stroke) can be implemented in the space-time dynamics of the system. Namely, we have to represent quanta of information, usually TRUE and FALSE values of a Boolean variable, routes of information transmission, and logic gates—where information quanta are processed—in states of the given system. That is, a primitive logical circuit should be constructed. This can be done in two ways.

First, a Boolean circuit could be embedded into a system in such a manner that all elements of the circuit are represented by the system's stationary states; the architecture is static and its topology is essential for a computation. We would call this an architecture-based universality.

Second, we could adopt techniques of a dynamic or collision-based computing that employs finite patterns—mobile self-localized excitations—which travel in space and execute computation when they collide with each other. Truth values of logical variables are represented by the absence of traveling information quanta or by various states of the quanta. There are no predetermined wires: patterns can travel anywhere in the medium; a trajectory of a pattern motion is analogous to a instantaneous wire. A typical interaction gate has two input "wires" (trajectories of the colliding mobile localizations) and, typically, three output "wires" (two "wires" represent the localizations' trajectories when they continue their motion undisturbed, the third output gives a trajectory of a new localization, formed in the result of the collision of two incoming localizations).