Paper by Erik D. Demaine
- Hamed Mohtasham Shad, Rose Morris-Wright, Erik D. Demaine, Sándor P. Fekete, and Aaron Becker, “Particle computation: Device fan-out and binary memory”, in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 2015), Seattle, Washington, May 26–30, 2015, pages 5384–5389.
We present fundamental progress on the computational universality of swarms of
micro- or nano-scale robots in complex environments, controlled not by
individual navigation, but by a uniform global, external force. Consider a 2D
grid world, in which all obstacles and robots are unit squares, and for each
actuation, robots move maximally until they collide with an obstacle or
another robot. In previous work, we demonstrated components of particle
computation in this world, designing obstacle configurations that implement
and and or logic gates: by using dual-rail logic, we
designed not, nor, nand, xor, xnor
logic gates. However, we were unable to design a fan-out gate, which
is necessary for simulating the full range of complex interactions that are
present in arbitrary digital circuits. In this work we resolve this problem by
proving unit-sized robots cannot generate a fan-out gate. On
the positive side, we resolve the missing component with the help of $2 \times
1$ robots, which can create fan-out gates that produce multiple copies of the
inputs. Using these gates we are able to establish the full range of
computational universality as presented by complex digital circuits. As an
example we connect our logic elements to produce a 3-bit counter. We also
demonstrate how to implement a data storage element.
- The paper is available in PDF (846k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated November 16, 2017 by