Computability in Amorphous Structures.

Amorphous computing differs from the classical ideas about computations almost in every aspect. The architecture of amorphous computers is random, since they consist of a plethora of identical computational units spread randomly over a given area. Within a limited radius the units can communicate wirelessly with their neighbors via a single-channel radio. We consider a model whose assumptions on the underlying computing and communication abilities are among the weakest possible: all computational units are finite state probabilistic automata working asynchronously, there is no broadcasting collision detection mechanism and no network addresses. We show that under reasonable probabilistic assumptions non-uniform families of such amorphous computers can possess universal computing power with a high probability. To the best of our knowledge this is the first result showing the universality of such computing systems. [ABSTRACT FROM AUTHOR]