The evolution of emergent computation

A simple evolutionary process can discover sophisticated methods for emergent information-processing in decentralized spatially-extended systems. The mechanisms underlying the resulting emergent computation are explicated by a novel technique for analyzing particle-based logic embedded in pattern-forming systems. Understanding how globally-coordinated computation can emerge in evolution is relevant both for the scientific understanding of natural information processing and for engineering new forms of parallel computing systems. * Correspondence author. Many systems in nature exhibit sophisticated collective information-processing abilities that emerge from the individual actions of simple components interacting via restricted communica-tion pathways. Some often-cited examples include efficient foraging and intricate nest-building in insect societies (1), the spontaneous aggregation of a reproductive multicellular organism from individual amoeba in the life cycle of the Dictyostelium slime mold (2), the parallel and distributed processing of sensory information by assemblies of neurons in the brain (3), and the optimal pricing of goods in an economy arising from agents obeying local rules of commerce (4). Allowing global coordination to emerge from a decentralized collection of simple component