Paper by Erik D. Demaine

Reference:

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.

Abstract:

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 × 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.

Availability:

The paper is available in PDF (846k).

See information on file formats.

[Google Scholar search]