Amorphous computing

Amorphous computing refers to computational systems that use very large numbers of identical, parallel processors each having limited computational ability and local interactions. The term Amorphous Computing was coined at MIT in 1996 in a paper entitled "Amorphous Computing Manifesto" by Abelson, Knight, Sussman, et al.

Examples of naturally occurring amorphous computations can be found in many fields, such as: developmental biology (the development of multicellular organisms from a single cell), molecular biology (the organization of sub-cellular compartments and intra-cell signaling), neural networks, and chemical engineering (non-equilibrium systems) to name a few. The study of amorphous computation is hardware agnostic -- it is not concerned with the physical substrate (biological, electronic, nanotech, etc.) but rather with the characterization of amorphous algorithms as abstractions with the goal of both understanding existing natural examples and engineering novel systems.

Amorphous computers tend to have many of the following properties:

Algorithms, tools, and patterns

(Some of these algorithms have no known names. Where a name is not known, a descriptive one is given.)

Researchers and labs

Documents

  1. The Amorphous Computing Home Page
    A collection of papers and links at the MIT AI lab
  2. Amorphous Computing (Communications of the ACM, May 2000)
    A review article showing examples from Coore's Growing Point Language as well as patterns created from Weiss's rule triggering language.
  3. Amorphous Computing Slides from DARPA talk in 1998
    An overview of ideas and proposals for implementations
  4. Amorphous and Cellular Computing PPT from 2002 NASA Lecture
    Almost the same as above, in PPT format
  5. Infrastructure for Engineered Emergence on Sensor/Actuator Networks, Beal and Bachrach, 2006.
    An amorphous computing language called "Proto".
  6. Self-repairing Topological Patterns Clement, Nagpal.
    Algorithms for self-repairing and self-maintaining line.
  7. Robust Methods of Amorphous Synchronization, Joshua Grochow
    Methods for inducing global temporal synchronization.
  8. Programmable Self-Assembly: Constructing Global Shape Using Biologically-Inspired Local Interactions and Origami Mathematics and Associated Slides Nagpal PhD Thesis
    A language to compile local-interaction instructions from a high-level description of an origami-like folded structure.
  9. Towards a Programmable Material, Nagpal Associated Slides
    Similar outline to previous paper
  10. Self-Healing Structures in Amorphous Computing Zucker
    Methods for detecting and maintaining topologies inspired by biological regeneration.
  11. Resilient serial execution on amorphous machines, Sutherland Master's Thesis
    A language for running serial processes on amorphous computers
  12. Paradigms for Structure in an Amorphous Computer, 1997 Coore, Nagpal, Weiss
    Techniques for creating hierarchical order in amorphous computers.
  13. Organizing a Global Coordinate System from Local Information on an Amorphous Computer, 1999 Nagpal.
    Techniques for creating coordinate systems by gradient formation and analyzes precision limits.
  14. Amorphous Computing: examples, mathematics and theory, 2013 W Richard Stark.
    This paper presents nearly 20 examples varying from simple to complex, standard mathematical tools are used to prove theorems and compute expected behavior, four programming styles are identified and explored, three uncomputability results are proved, and the computational foundations of a complex, dynamic intelligence system are sketched.