Mechanisms of emergent computation in cellular automata

Lecture notes in computer sciencePublished 1 January 1998

Wim Hordijk, James P. Crutchfield, Melanie Mitchell

DOI10.1007/bfb0056903

Source URL

Citations64

SJR quartileQ2

SJR score0.35

SNIP0.55

TL;DR

The results show, via a close quantitative agreement, that the embedded-particle framework captures the main information processing mechanisms of the emergent computation that arise in these evolved CAs.

Abstract

We introduce a class of embedded-particle models for describing the emergent computational strategies observed in cellular automata (CAs) that were evolved for performing certain computational tasks. The models are evaluated by comparing their estimated performances with the actual performances of the CAs they model. The results show, via a close quantitative agreement, that the embedded-particle framework captures the main information processing mechanisms of the emergent computation that arise in these evolved CAs.

Keywords

Computer SciencePhysics and Astronomy

Physical Review LettersInferring statistical complexity

1,030 Citations1989James P. Crutchfield, Karl Young

A technique is presented that directly reconstructs minimal equations of motion from the recursive structure of measurement sequences, demonstrating a form of superuniversality that refers only to the entropy and complexity of a data stream.

Computers in PhysicsCellular Automata and Complexity

874 Citations1995Stephen Wolfram, A. John Mallinckrodt

Physica D Nonlinear PhenomenaThe calculi of emergence: computation, dynamics and induction

770 Citations1994James P. Crutchfield

An overview of an inductive framework-hierarchical ϵ-machine reconstruction—in which the emergence of complexity is associated with the innovation of new computational model classes is presented, along with an analysis of the constraints on the dynamics of innovation.

Physica D Nonlinear PhenomenaComputational mechanics of cellular automata: An example

172 Citations1997James Hanson, James P. Crutchfield

The techniques of computational mechanics are extended and the emergence time at which the space-time behavior condenses into configurations consisting only of domains, particles, and particle interactions are defined.

Lecture notes in computer scienceA genetic algorithm discovers particle-based computation in cellular automata

153 Citations1994Rajarshi Das, Melanie Mitchell +1 more

The emergent logic underlying these strategies are analyzed in terms of information processing performed by “particles” in space-time, and the generational progression of the GA evolution of these strategies is described.

PDXScholar (Portland State University)Evolving Globally Synchronized Cellular Automata

139 Citations1995Rajarshi Das, James P. Crutchfield +2 more

This work shows that the evolution of spontaneous synchronization, one type of emergent coordination, takes advantage of the underlying medium's potential to form embedded particles, and describes one typical solution discovered by the GA, delineating the discovered synchronization algorithm in terms of embedded particles and their interactions.

View PDF

Journal of Statistical PhysicsThe attractor?basin portrait of a cellular automaton

135 Citations1992James Hanson, James P. Crutchfield

The attractor-basin portrait of nonlinear elementary CA rule 18 is described, whose global dynamics is largely determined by a single regular attracting domain, and it is confirmed that in rule 18, isolated dislocation trajectories, as well as a dislocation gas, agree extremely well with the classical model of annihilating diffusive particles.

Physica D Nonlinear PhenomenaTurbulent pattern bases for cellular automata

111 Citations1993James P. Crutchfield, James Hanson

The decompostion technique is illustrated by analyzing a binary, range-2 cellular automaton having two invariant chaotic domains of different complexities and entropies, and how to construct a finite-state transducer that performs nonlinear spatial filtering such that the resulting space-time patterns reveal the domains and the intervening walls and dislocations.