%ABecker, Aaron%ADemaine, Erik%AFekete, SÃ¡ndor%ALonsford, Jarrett%AMorris-Wright, Rose%BJournal Name: Natural Computing
%D2017%I
%JJournal Name: Natural Computing
%K
%MOSTI ID: 10048937
%PMedium: X
%TParticle computation: complexity, algorithms, and logic
%XWe investigate algorithmic control of a large swarm of mobile particles (such as robots, sensors, or building material) that
move in a 2D workspace using a global input signal (such as gravity or a magnetic field). Upon activation of the field, each
particle moves maximally in the same direction until forward progress is blocked by a stationary obstacle or another
stationary particle. In an open workspace, this system model is of limited use because it has only two controllable degrees
of freedomâ€”all particles receive the same inputs and move uniformly. We show that adding a maze of obstacles to the
environment can make the system drastically more complex but also more useful. We provide a wide range of results for a
wide range of questions. These can be subdivided into external algorithmic problems, in which particle configurations
serve as input for computations that are performed elsewhere, and internal logic problems, in which the particle configurations
themselves are used for carrying out computations. For external algorithms, we give both negative and positive
results. If we are given a set of stationary obstacles, we prove that it is NP-hard to decide whether a given initial
configuration of unit-sized particles can be transformed into a desired target configuration. Moreover, we show that finding
a control sequence of minimum length is PSPACE-complete. We also work on the inverse problem, providing constructive
algorithms to design workspaces that efficiently implement arbitrary permutations between different configurations. For
internal logic, we investigate how arbitrary computations can be implemented. We demonstrate how to encode dual-rail
logic to build a universal logic gate that concurrently evaluates AND, NAND, NOR, and OR operations. Using many of these
gates and appropriate interconnects, we can evaluate any logical expression. However, we establish that simulating the full
range of complex interactions present in arbitrary digital circuits encounters a fundamental difficulty: a FAN-OUT gate cannot
be generated. We resolve this missing component with the help of 2 9 1 particles, which can create FAN-OUT gates that
produce multiple copies of the inputs. Using these gates we provide rules for replicating arbitrary digital circuits.
%0Journal Article