Particle-Based Computation
27 Feb 2017 16:30
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.]
