Particle-Based Computation
Last update: 21 Apr 2025 21:17
First version:
That is, constructing computational processes out of the interactions of
spatially-localized, temporally-persisting, mobile blobs of activity or
stuff, in whatever sense of "stuff" or "activity" may be appropriate.
This is a pretty standard trick for studying cellular automata, though
there's some evidence it shows up in the real world (see Peak et al. below,
which I've discussed in detail elsewhere).
It's especially interesting because it seems to show up a lot when you evolve local, decentralized rules to perform
global computations.
Recommended:
- Wim Hordijk, CRS and James P. Crutchfield, "Upper Bound on the
Products of Particle Interactions in Cellular Automata", Physica
D 154 (2001): 240--258 = nlin.CG/0008038 [Bad form, I
know, but I have two excuses. One is that this is really Wim's result, with
Jim and I merely acting as assistants. The other is that we gave a reasonably
thorough bibliography on particles in cellular automata and their use as
computers. Since I don't feel sufficiently energetic right now to extract the
highlights, see the references therein. Besides, this is the only thing I've
ever written which has resulted in threats of legal action from a substantial
corporation.]
- David Peak, Jevin D. West, Susanna M. Messinger and Keith A. Mott,
"Evidence for complex, collective dynamics and emergent, distributed
computation in plants", Proceedings of the
National Academy of Sciences (USA) 101 (2004):
918--922
- Thimo Rohlf and Stefan Bornholdt
- "Self-organized pattern formation and noise-induced control
from particle computation",
cond-mat/0312366 [Short
version]
- "Morphogenesis by coupled regulatory networks", q-bio.MN/0401024 [Long
version, which includes discussion of how to implement the CA rule by means of
highly stylized gene regulatory
networks]
To read:
- Andrew Adamatzky
- Computing in Nonlinear Media and Automata
Collectives [Adamatzky's
book-page]
- (ed.), Collison-Based Computing
- P. Coullet, C. Toniolo and C. Tresser, "How much information can
one store in a non-equilibrium medium?", nlin.CD/0503011 = Chaos 14
(2004): 839--844
- Jerome Durand-Lose, "Abstract geometrical computation for black
hole computation", pp. 176--187 in Machines, Computations, and
Universality (Springer Lecture Notes in Computer Science, vol. 3354) [PDF
preprint. As he says, the stuff about black holes is merely analogical ---
it's really about formalizing particle-based computation in continuous spaces.]