  In this work, we study theoretical models of \emph{programmable matter}
systems. The systems under consideration consist of spherical modules, kept
together by magnetic forces and able to perform two minimal mechanical
operations (or movements): \emph{rotate} around a neighbor and \emph{slide}
over a line. In terms of modeling, there are $n$ nodes arranged in a
2-dimensional grid and forming some initial \emph{shape}. The goal is for the
initial shape $A$ to \emph{transform} to some target shape $B$ by a sequence of
movements. Most of the paper focuses on \emph{transformability} questions,
meaning whether it is in principle feasible to transform a given shape to
another. We first consider the case in which only rotation is available to the
nodes. Our main result is that deciding whether two given shapes $A$ and $B$
can be transformed to each other, is in $\mathbf{P}$. We then insist on
rotation only and impose the restriction that the nodes must maintain global
connectivity throughout the transformation. We prove that the corresponding
transformability question is in $\mathbf{PSPACE}$ and study the problem of
determining the minimum \emph{seeds} that can make feasible, otherwise
infeasible transformations. Next we allow both rotations and slidings and prove
universality: any two connected shapes $A,B$ of the same order, can be
transformed to each other without breaking connectivity. The worst-case number
of movements of the generic strategy is $\Omega(n^2)$. We improve this to
$O(n)$ parallel time, by a pipelining strategy, and prove optimality of both by
matching lower bounds. In the last part of the paper, we turn our attention to
distributed transformations. The nodes are now distributed processes able to
perform communicate-compute-move rounds. We provide distributed algorithms for
a general type of transformations.
