  We investigate computational issues in the distributed model Amoebots of
programmable matter. In this model, the computational entities, called
particles, are anonymous finite-state machines that operate and move on an
hexagonal tasselation of the plane. In this paper we show how a constant number
of such weak particles can simulate a powerful Turing-complete entity that is
able to move on the plane while computing. We then show an application of our
tool to the classical Shape-Formation problem, providing a new and much more
general distributed solution protocol. Indeed, the existing algorithms would
allow to form only shapes made of arrangements of segments and triangles. Our
algorithm allows the particles to form more abstract and general connected
shapes, including circles and spirals, as well as fractal objects of
non-integer dimension, such as the Sierpinski triangle or the Koch snowflake.
In lieu of the existing limitation on the formability of a shape depending on
the symmetry of the initial configuration of the particles, our result provides
a complete characterization of the connected shapes that can be formed by an
initially simply connected set of particles. Furthermore, in the case of
non-connected shapes, we give almost-matching necessary and sufficient
conditions for their formability.
