Preface: Dynamics of Evolutionary Processes (2009)
James P. Crutchfield, Peter Schuster
Starting with a brief historical introduction, we review recent results in the theory of evolutionary dynamics, emphasizing new mathematical and simulation methods that promise to provide...
Information Accessibility and Cryptic Processes: Linear Combinations of Causal States (2009)
Mahoney, John R., Ellison, Christopher J., Crutchfield, James P.
We show in detail how to determine the time-reversed representation of a stationary hidden stochastic process from linear combinations of its forward-time $\epsilon$-machine causal states. This also...
Information Accessibility and Cryptic Processes (2009)
Mahoney, John R., Ellison, Christopher J., Crutchfield, James P.
We give a systematic expansion of the crypticity--a recently introduced measure of the inaccessibility of a stationary process's internal state information. This leads to a hierarchy of k-cryptic...
Prediction, Retrodiction, and The Amount of Information Stored in the Present (2009)
Ellison, Christopher J., Mahoney, John R., Crutchfield, James P.
We introduce an ambidextrous view of stochastic dynamical systems, comparing their forward-time and reverse-time representations and then integrating them into a single time-symmetric representation....
Entomogenic Climate Change: Insect Bioacoustics and Future Forest Ecology (2009)
David D. Dunn, James P. Crutchfield
Leonardo - Volume 42, Number 3, June 2009
Time's Barbed Arrow: Irreversibility, Crypticity, and Stored Information (2009)
Crutchfield, James P., Ellison, Christopher J., Mahoney, John R.
We show why the amount of information communicated between the past and future--the excess entropy--is not in general the amount of information stored in the present--the statistical complexity. This...
Feldman, David P., McTague, Carl S., Crutchfield, James P.
Intrinsic computation refers to how dynamical systems store, structure, and transform historical and spatial information. By graphing a measure of structural complexity against a measure of...
Entomogenic Climate Change (2008)
Dunn, David, Crutchfield, James P.
Rapidly expanding insect populations, deforestation, and global climate change threaten to destabilize key planetary carbon pools, especially the Earth's forests which link the micro-ecology of...
Optimal Causal Inference (2008)
Susanne Still, James P. Crutchfield, Christopher J. Ellison
We consider an information-theoretic objective function for statistical modeling of time series that embodies a parametrized trade-off between the predictive power of a model and the model’s...
Computation in Sofic Quantum Dynamical Systems (2008)
Karoline Wiesner, James P. Crutchfield
Abstract. We analyze how measured quantum dynamical systems store and process information, introducing sofic quantum dynamical systems. Using recently introduced information-theoretic measures for...
Intrinsic quantum computation (2008)
Crutchfield, James P., Wiesner, Karoline
We introduce ways to measure information storage in quantum systems, using a recently introduced computation-theoretic model that accounts for measurement effects. The first, the quantum excess...
The Evolutionary Design of Collective Computation in Cellular Automata (2007)
James P. Crutchfield, Melanie Mitchell, Rajarshi Das
. We investigate the ability of a genetic algorithm to design cellular automata that perform computations. The computational strategies of the resulting cellular automata can be understood using a...
Any Radius UIUC-BI-CCSR-92-08 (2007)
Modeling pattern data series with cellular automata fails for a wide range of deterministic nonlinear spatial processes. If the latter have finite spatially-local memory, reconstructed cellular...
Email: chaos @ gojira.berkeley.edu (2007)
James P. Crutchfield, Melanie Mitchell
A simple evolutionary process can discover sophisticated methods for emergent information-processing in decentralized spatially-extended systems. The mechanisms underlying the resulting emergent...
Definitions of Regular Attractor (2007)
James E. Hanson, James P. Crutchfield
The definition of regular attractor, originally presented in The Attractor-Basin Portrait of a Cellular Automaton,Ill is reexamined and improved.
Optimal Causal Inference (2007)
Still, Susanne, Crutchfield, James P., Ellison, Christopher J.
We consider an information-theoretic objective function for statistical modeling of time series that embodies a parametrized trade-off between the predictive power of a model and the model's...
Still, Susanne, Crutchfield, James P.
We show how rate-distortion theory provides a mechanism for automated theory building by naturally distinguishing between regularity and randomness. We start from the simple principle that model...
Strelioff, Christopher C., Crutchfield, James P., Huebler, Alfred W.
Markov chains are a natural and well understood tool for describing one-dimensional patterns in time or space. We show how to infer kth order Markov chains, for arbitrary k, from finite data by...
Primordial Evolution in the Finitary Process Soup (2007)
Gornerup, Olof, Crutchfield, James P.
A general and basic model of primordial evolution--a soup of reacting finitary and discrete processes--is employed to identify and analyze fundamental mechanisms that generate and maintain complex...
Computation in Sofic Quantum Dynamical Systems (2007)
Wiesner, Karoline, Crutchfield, James P.
We analyze how measured quantum dynamical systems store and process information, introducing sofic quantum dynamical systems. Using recently introduced information-theoretic measures for quantum...
Strelioff, Christopher C., Crutchfield, James P., Hubler, Alfred W.
Markov chains are a natural and well understood tool for describing one-dimensional patterns in time or space. We show how to infer $k$-th order Markov chains, for arbitrary $k$, from finite data by...
David J. Albers, David J. Albers, Postdoctoral Scholar, James P. Crutchfield, Postdoctoral Scholar, James P. Crutchfield
RESEARCH INTERESTS: dynamical systems (both abstract and computational); learning theory; game theory; ergodic theory; random matrix theory; random dynamical systems; computational fluid mechanics,...
Dunn, David, Crutchfield, James P.
Accumulating observational evidence suggests an intimate connection between rapidly expanding insect populations, deforestation, and global climate change. We review the evidence, emphasizing the...
Intrinsic Quantum Computation (2006)
Crutchfield, James P., Wiesner, Karoline
We introduce ways to measure information storage in quantum systems, using a recently introduced computation-theoretic model that accounts for measurement effects. The first, the quantum excess...
Language Diversity of Measured Quantum Processes (2006)
Wiesner, Karoline, Crutchfield, James P.
The behavior of a quantum system depends on how it is measured. How much of what is observed comes from the structure of the quantum system itself and how much from the observer's choice of...
Strelioff, Christopher C., Crutchfield, James P.
Symbolic dynamics has proven to be an invaluable tool in analyzing the mechanisms that lead to unpredictability and random behavior in nonlinear dynamical systems. Surprisingly, a discrete partition...
Infinite Correlation in Measured Quantum Processes (2006)
Wiesner, Karoline, Crutchfield, James P.
We show that quantum dynamical systems can exhibit infinite correlations in their behavior when repeatedly measured. We model quantum processes using quantum finite-state generators and take the...
Computation in Finitary Stochastic and Quantum Processes (2006)
Wiesner, Karoline, Crutchfield, James P.
We introduce stochastic and quantum finite-state transducers as computation-theoretic models of classical stochastic and quantum finitary processes. Formal process languages, representing the...
Hierarchical Self-Organization in the Finitary Process Soup (2006)
Goernerup, Olof, Crutchfield, James P.
Current analyses of genomes from numerous species show that the diversity of organism's functional and behavioral characters is not proportional to the number of genes that encode the organism. We...
Design and Development of Bendway Weirs for the Dogtooth Bend Reach, Mississippi River (2006)
Derrick, David L., Boyd, Marden B., Crutchfield, James P., Henderson, Raymond R.
This investigation is one of a series of model studies used to determine the effectiveness of various dike and bendway weir systems proposed for the improvement of several troublesome reaches on the...
The Dynamics of Learning and the Emergence of Distributed Adaption (2006)
This project developed fundamental theory and novel algorithms for adaptive learning in autonomous collective-agent systems. The first goal was to develop a new mathematical framework for analyzing...
McTague, Carl S., Crutchfield, James P.
In the computational-mechanics structural analysis of one-dimensional cellular automata the following automata-theoretic analogue of the \emph{change-point problem} from time series analysis arises:...
Stability and Diversity in Collective Adaptation (2004)
Sato, Yuzuru, Akiyama, Eizo, Crutchfield, James P.
We derive a class of macroscopic differential equations that describe collective adaptation, starting from a discrete-time stochastic microscopic model. The behavior of each agent is a dynamic...
Stability and Diversity in Collective Adaptation (2004)
Sato, Yuzuru, Akiyama, Eizo, Crutchfield, James P.
We derive a class of macroscopic differential equations that describe collective adaptation, starting from a discrete-time stochastic microscopic model. The behavior of each agent is a dynamic...
Objects That Make Objects: The Population Dynamics of Structural Complexity (2004)
Crutchfield, James P., Gornerup, Olof
To analyze the evolutionary emergence of structural complexity in physical processes we introduce a general, but tractable, model of objects that interact to produce new objects. Since the...
Reductions of Hidden Information Sources (2004)
Ay, Nihat, Crutchfield, James P.
In all but special circumstances, measurements of time-dependent processes reflect internal structures and correlations only indirectly. Building predictive models of such hidden information sources...
Stability and Diversity in Collective Adaptation (2004)
Sato, Yuzuru, Akiyama, Eizo, Crutchfield, James P.
We derive a class of macroscopic differential equations that describe collective adaptation, starting from a discrete-time stochastic microscopic model. The behavior of each agent is a dynamic...
Stability and Diversity in Collective Adaptation (2004)
Sato, Yuzuru, Akiyama, Eizo, Crutchfield, James P.
We derive a class of macroscopic differential equations that describe collective adaptation, starting from a discrete-time stochastic microscopic model. The behavior of each agent is a dynamic...
R.: The evolutionary design of collective computation in cellular automata (2003)
James P. Crutchfield, Melanie Mitchell, Rajarshi Das, Evolutionary Dynamics—exploring The
Abstract. We investigate the ability of a genetic algorithm to design cellular automata that perform computations. The computational strategies of the resulting cellular automata can be understood...
Structural Information in Two-Dimensional Patterns: Entropy Convergence and Excess Entropy (2002)
Feldman, David P., Crutchfield, James P.
We develop information-theoretic measures of spatial structure and pattern in more than one dimension. As is well known, the entropy density of a two-dimensional configuration can be efficiently and...
An Algorithm for Pattern Discovery in Time Series (2002)
Shalizi, Cosma Rohilla, Shalizi, Kristina Lisa, Crutchfield, James P.
We present a new algorithm for discovering patterns in time series and other sequential data. We exhibit a reliable procedure for building the minimal set of hidden, Markovian states that is...
Feldman, David P., Crutchfield, James P.
We analyze how difficult it is to synchronize to a periodic sequence whose structure is known, when an observer is initially unaware of the sequence's phase. We examine the transient information T, a...
Coupled Replicator Equations for the Dynamics of Learning in Multiagent Systems (2002)
Sato, Yuzuru, Crutchfield, James P.
Starting with a group of reinforcement-learning agents we derive coupled replicator equations that describe the dynamics of collective learning in multiagent systems. We show that, although agents...
What Lies Between Order and Chaos? (2002)
James P. Crutchfield, James P. Crutchfield
What is a pattern? How do we come to recognize patterns that we’ve never seen before? Formalizing and quantifying the notion of pattern and the process of pattern discovery go right to the heart of...
Synchronizing to the Environment: Information Theoretic Constraints on Agent Learning (2001)
Crutchfield, James P., Feldman, David P.
We show that the way in which the Shannon entropy of sequences produced by an information source converges to the source's entropy rate can be used to monitor how an intelligent agent builds and...
Regularities Unseen, Randomness Observed: Levels of Entropy Convergence (2001)
Crutchfield, James P., Feldman, David P.
We study how the Shannon entropy of sequences produced by an information source converges to the source's entropy rate. We synthesize several phenomenological approaches to applying information...
Upper Bound on the Products of Particle Interactions in Cellular Automata (2000)
Hordijk, Wim, Shalizi, Cosma Rohilla, Crutchfield, James P.
Particle-like objects are observed to propagate and interact in many spatially extended dynamical systems. For one of the simplest classes of such systems, one-dimensional cellular automata, we...
Shalizi, Cosma Rohilla, Crutchfield, James P.
Discovering relevant, but possibly hidden, variables is a key step in constructing useful and predictive theories about the natural world. This brief note explains the connections between three...
Pattern Discovery and Computational Mechanics (2000)
Shalizi, Cosma Rohilla, Crutchfield, James P.
Computational mechanics is a method for discovering, describing and quantifying patterns, using tools from statistical physics. It constructs optimal, minimal models of stochastic processes and their...
Resource sharing and coevolution in evolving cellular automata (2000)
Justin Werfel, Melanie Mitchell, James P. Crutchfield
Abstract—Coevolution, between a population of candidate solutions and a population of test cases, has received increasing attention as a promising biologically inspired method for improving the...
Resource sharing and coevolution in evolving cellular automata (2000)
Justin Werfel, Melanie Mitchell, James P. Crutchfield
Coevolution between a population of candidate solutions and a population of test cases has received increasing attention as a promising biologically inspired method for improving the performance of...
Resource Sharing and Coevolution in Evolving Cellular Automata (1999)
Werfel, Justin, Mitchell, Melanie, Crutchfield, James P.
Evolving one-dimensional cellular automata (CAs) with genetic algorithms has provided insight into how improved performance on a task requiring global coordination emerges when only local...
Computational Mechanics: Pattern and Prediction, Structure and Simplicity (1999)
Shalizi, Cosma Rohilla, Crutchfield, James P.
Computational mechanics, an approach to structural complexity, defines a process's causal states and gives a procedure for finding them. We show that the causal-state representation--an...
Metastable Evolutionary Dynamics: Crossing Fitness Barriers or Escaping via Neutral Paths? (1999)
Van Nimwegen, Erik, Crutchfield, James P.
We analytically study the dynamics of evolving populations that exhibit metastability on the level of phenotype or fitness. In constant selective environments, such metastable behavior is caused by...
Comment on "Simple Measure of Complexity" (1999)
Crutchfield, James P., Feldman, David P., Shalizi, Cosma Rohilla
We critique the measure of complexity introduced by Shiner, Davison, and Landsberg in Ref. [1]. In particular, we point out that it is over-universal, in the sense that it has the same dependence on...
Neutral Evolution of Mutational Robustness (1999)
Van Nimwegen, Erik, Crutchfield, James P., Huynen, Martijn
We introduce and analyze a general model of a population evolving over a network of selectively neutral genotypes. We show that the population's limit distribution on the neutral network is solely...
Neutral evolution of mutational robustness (1999)
Nimwegen, Erik Van, Crutchfield, James P., Huynen, Martijn
We introduce and analyze a general model of a population evolving over a network of selectively neutral genotypes. We show that the populations limit distribution on the neutral network is solely...
The Evolutionary Unfolding of Complexity (1999)
Crutchfield, James P., Van Nimwegen, Erik
We analyze the population dynamics of a broad class of fitness functions that exhibit epochal evolution---a dynamical behavior, commonly observed in both natural and artificial evolutionary...
Statistical dynamics of the Royal Road genetic algorithm (1999)
Erik Van Nimwegen, James P. Crutchfield, Melanie Mitchell
Metastability is a common phenomenon. Many evolutionary processes, both natural and artificial, alternate between periods of stasis and brief periods of rapid change in their behavior. In this paper...
Resource Sharing and Coevolution in Evolving Cellular Automata (1999)
Justin Werfel, Melanie Mitchell, James P. Crutchfield
Evolving one-dimensional cellular automata (CAs) with genetic algorithms has provided insight into how improved performance on a task requiring global coordination emerges when only local...
The Evolutionary Unfolding of Complexity (1999)
James P. Crutchfield, Erik Van Nimwegen
. We analyze the population dynamics of a broad class of fitness functions that exhibit epochal evolution---a dynamical behavior, commonly observed in both natural and artificial evolutionary...
Computational mechanics: Pattern and prediction, structure and simplicity (1999)
Cosma Rohilla Shalizi, James P. Crutchfield
Computational mechanics, an approach to structural complexity, defines a process’s causal states and gives a procedure for finding them. We show that the causal-state representation—an...
Statistical dynamics of the Royal Road genetic algorithm (1999)
Erik Van Nimwegen, James P. Crutchfield, Melanie Mitchell
Metastability is a common phenomenon. Many evolutionary processes, both natural and artificial, alternate between periods of stasis and brief periods of rapid change in their behavior. In this paper...
Inventory of River Training Structures in Shallow-Draft Waterways. (1998)
Derrick, David L., Gernand, Herbert W., Crutchfield, James P.
The repair of deep- and shallow-draft training structures has continued to be a significant maintenance cost for structures maintained by the US Army Corps of Engineers. This maintenance includes the...
Discovering Coherent Structures in Nonlinear Spatial Systems. (1998)
This Final Technical Report reviews our work on the automated discovery of coherent structures in spatial dynamical systems.
Optimizing Epochal Evolutionary Search: Population-Size Independent Theory (1998)
Van Nimwegen, Erik, Crutchfield, James P.
Epochal dynamics, in which long periods of stasis in population fitness are punctuated by sudden innovations, is a common behavior in both natural and artificial evolutionary processes. We use a...
Optimizing Epochal Evolutionary Search: Population-Size Dependent Theory (1998)
Van Nimwegen, Erik, Crutchfield, James P.
Epochal dynamics, in which long periods of stasis in an evolving population are punctuated by a sudden burst of change, is a common behavior in both natural and artificial evolutionary processes. We...
The Evolutionary Design of Collective Computation in Cellular Automata (1998)
Crutchfield, James P., Mitchell, Melanie, Das, Rajarshi
We investigate the ability of a genetic algorithm to design cellular automata that perform computations. The computational strategies of the resulting cellular automata can be understood using a...
Crutchfield, James P., Shalizi, Cosma Rohilla
Thermodynamic depth is an appealing but flawed structural complexity measure. It depends on a set of macroscopic states for a system, but neither its original introduction by Lloyd and Pagels nor any...
Mechanisms of Emergent Computation in Cellular Automata (1998)
Wim Hordijk, James P. Crutchfield, Melanie Mitchell
. 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...
The Evolutionary Design of Collective Computation in Cellular Automata (1998)
James P. Crutchfield, Melanie Mitchell, Rajarshi Das
. We investigate the ability of a genetic algorithm to design cellular automata that perform computations. The computational strategies of the resulting cellular automata can be understood using a...
The Evolutionary Design of Collective Computation in Cellular Automata (1998)
James P. Crutchfield, Melanie Mitchell, Rajarshi Das
We investigate the ability of a genetic algorithm to design cellular automata that perform computations. The computational strategies of the resulting cellular automata can be understood using a...
Statistical Dynamics of the Royal Road Genetic Algorithm (1998)
Erik Nimwegen, James P. Crutchfield, Melanie Mitchell
. Metastability is a common phenomenon. Many evolutionary processes, both natural and artificial, alternate between periods of stasis and brief periods of rapid change in their behavior. In this...
Mechanisms of emergent computation in cellular automata (1998)
Wim Hordijk, James P. Crutchfield, Melanie Mitchell
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...
Statistical Measures of Complexity: Why? (1997)
Feldman, David P., Crutchfield, James P.
We review several statistical complexity measures proposed over the last decade and a half as general indicators of structure or correlation. Recently, Lopez-Ruiz, Mancini, and Calbet [Phys. Lett. A...
Quantum Automata and Quantum Grammars (1997)
Moore, Cristopher, Crutchfield, James P.
To study quantum computation, it might be helpful to generalize structures from language and automata theory to the quantum case. To that end, we propose quantum versions of finite-state and...
Statistical Complexity of Simple 1D Spin Systems (1997)
Crutchfield, James P., Feldman, David P.
We present exact results for two complementary measures of spatial structure generated by 1D spin systems with finite-range interactions. The first, excess entropy, measures the apparent spatial...
Finite Populations Induce Metastability in Evolutionary Search (1997)
Erik Van Nimwegen, James P. Crutchfield, Melanie Mitchell
We introduce an analytical model that predicts the dynamics of a simple evolutionary algorithm in terms of the flow in the space of fitness distributions. In the limit of infinite populations the...
Statistical Dynamics of the Royal Road Genetic Algorithm (1997)
Erik Van Nimwegen, James P. Crutchfield, Melanie Mitchell
. Metastability is a common phenomenon. Many evolutionary processes, both natural and artificial, alternate between periods of stasis and brief periods of rapid change in their behavior. In this...
Computational Mechanics of Cellular Automata: An Example (1997)
Proceedings Of The, James E. Hanson, James P. Crutchfield
We illustrate and extend the techniques of computational mechanics in explicating the structures that emerge in the space-time behavior of elementary one-dimensional cellular automaton rule 54. The...
Evolving cellular automata with genetic algorithms: A review of recent work (1996)
Melanie Mitchell, James P. Crutchfield, Rajarshi Das
We review recent work done by our group on applying genetic algorithms (GAs) to the design of cellular automata (CAs) that can perform computations requiring global coordination. A GA was used to...
Embedded-Particle Computation in Evolved Cellular Automata (1996)
Wim Hordijk, James P. Crutchfield, Melanie Mitchell
this paper we focus on how these CAs implement the emergent computational strategies for performing a task. In particular, we develop a class of embedded-particle models to describe the computational...
Evolving Cellular Automata with Genetic Algorithms: A Review of Recent Work (1996)
Melanie Mitchell, James P. Crutchfield, R. Das, Rajarshi Das
We review recent work done by our group on applying genetic algorithms (GAs) to the design of cellular automata (CAs) that can perform computations requiring global coordination. A GA was used to...
Evolving Globally Synchronized Cellular Automata (1995)
Rajarshi Das, James P. Crutchfield, Melanie Mitchell, James E. Hanson
How does an evolutionary process interact with a decentralized, distributed system in order to produce globally coordinated behavior? Using a genetic algorithm (GA) to evolve cellular automata (CAs),...
Evolving Globally Synchronized Cellular Automata (1995)
Rajarshi Das, James P. Crutchfield, Melanie Mitchell, James E. Hanson
How does an evolutionary process interact with a decentralized, distributed system in order to produce globally coordinated behavior? Using a genetic algorithm (GA) to evolve cellular automata (CAs),...
The evolution of emergent computation (1995)
James P. Crutchfield, Melanie Mitchell
A simple evolutionary process can discover sophisticated methods for emergent information-processing in decentralized spatially-extended systems. The mechanisms underlying the resulting emergent...
Evolving globally synchronized cellular automata (1995)
Rajarshi Das, James P. Crutchfield, Melanie Mitchell, James E. Hanson
How does an evolutionary process interact with a decentralized, distributed system in order to produce globally coordinated behavior? Using a genetic algorithm (GA) to evolve cellular automata (CAs),...
Evolving cellular automata to perform computations: Mechanisms and impediments (1994)
Melanie Mitchell, James P. Crutchfield, Peter T. Hraber
We present results from experiments in which a genetic algorithm (GA) was used to evolve cellular automata (CAs) to perform a particular computational task—one-dimensional density classification....
A genetic algorithm discovers particle-based computation in cellular automata (1994)
Rajarshi Das, Melanie Mitchell, James P. Crutchfield, In Y. Davidor, R. Männer (editors, ...
Abstract. How does evolution produce sophisticated emergent computation in systems composed of simple components limited to local interactions? To model such a process, we used a genetic algorithm...
Dynamics, computation, and the “edge of chaos”: A re-examination (1994)
Melanie Mitchell, James P. Crutchfield, Peter T. Hraber, In G. Cowan, D. Pines, D. Melzner (editors, ...
In this paper we review previous work and present new work concerning the relationship between dynamical systems theory and computation. In particular, we review work by Langton [21] and Packard [29]...
Is anything ever new? Considering emergence (1994)
James P. Crutchfield, J. P. Crutchfield
This brief essay reviews an approach to defining and then detecting the emergence of complexity in nonlinear processes. It is, in fact, a synopsis of Reference [1] that leaves out the technical...
Is Anything Ever New? - Considering Emergence (1994)
This brief essay reviews an approach to defining and then detecting the emergence of complexity in nonlinear processes. It is, in fact, a synopsis of Reference [1] that leaves out the technical...
Critical Computation, Phase Transitions, and Hierarchical Learning (1994)
James P. Crutchfield, J. P. Crutchfield
A study of the various routes to chaos in dynamical systems reveals that significant computation occurs at the onset of chaos. At first blush this is not surprising since statistical mechanics views...
The calculi of emergence: Computation, dynamics, and induction (1994)
Defining structure and detecting the emergence of complexity in nature are inherently subjective, though essential, scientific activities. Despite the difficulties, these problems can be analyzed in...
Revisiting the Edge of Chaos: Evolving Cellular Automata to Perform Computations (1993)
Mitchell, Melanie, Hraber, Peter, Crutchfield, James P.
We present results from an experiment similar to one performed by Packard (1988), in which a genetic algorithm is used to evolve cellular automata (CA) to perform a particular computational task....
Revisiting the edge of chaos: Evolving cellular automata to perform computations (1993)
Melanie Mitchell, Peter T. Hraber, James P. Crutchfield
We present results from an experiment similar to one performed by Packard [24], in which a genetic algorithm is used to evolve cellular automata (CA) to perform a particular computational task....
Fluctuation spectroscopy (1993)
W. Ebeling, Karl Young, James P. Crutchfield
We review the thermodynamics of estimating the statistical fluctuations of an observed process. Since any statistical analysis involves a choice of model class-- either explicitly or implicitly-- we...
Dynamics, Computation, and the "Edge of Chaos": A Re-Examination (1993)
Melanie Mitchell, James P. Crutchfield, Peter T. Hraber
In this paper we review previous work and present new work concerning the relationship between dynamical systems theory and computation. In particular, we review work by Langton [21] and Packard [29]...
Turbulent Pattern Bases for Cellular Automata (1993)
James P. Crutchfield, James E. Hanson
Unpredictable patterns generated by cellular automata (CA) can be decomposed with respect to a turbulent, positive entropy rate pattern basis. The resulting filtered patterns uncover significant...
Turbulent Pattern Bases for Cellular Automata (1993)
James P. Crutchfield, James E. Hanson
Unpredictable patterns generated by cellular automata (CA) can be decomposed with respect to a turbulent, positive entropy rate pattern basis. The resulting filtered patterns uncover significant...
Revisiting the Edge of Chaos: Evolving Cellular Automata to Perform Computations (1993)
Melanie Mitchell, Peter T. Hraber, James P. Crutchfield
We present results from an experiment similar to one performed by Packard [24], in which a genetic algorithm is used to evolve cellular automata (CA) to perform a particular computational task....
Discovering Coherent Structures in Nonlinear Spatial Systems (1992)
A synthesis of elementary computation and dynamical system theories leads to a constructive approach to discovering coherent structures in spatial systems and to quantifying a pattern's...
Semantics and Thermodynamics (1992)
James P. Crutchfield, J. P. Crutchfield
Inferring models from given data leads through many different changes in representation. Most are subtle and profitably ignored. Nonetheless, any such change affects the semantic content of the...
Neutral evolution of mutational robustness
Van Nimwegen, Erik, Crutchfield, James P., Huynen, Martijn
We introduce and analyze a general model of a population evolving over a network of selectively neutral genotypes. We show that the population’s limit distribution on the neutral network is solely...
Neutral evolution of mutational robustness
Van Nimwegen, Erik, Crutchfield, James P., Huynen, Martijn
We introduce and analyze a general model of a population evolving over a network of selectively neutral genotypes. We show that the population’s limit distribution on the neutral network is solely...
Synchronizing to the Environment: Information Theoretic Constraints on Agent Learning
James P. Crutchfield, David P. Feldman
We show that the way in which the Shannon entropy of sequences produced by an information source converges to the source's entropy rate can be used to monitor how an intelligent agent builds and...
Regularities Unseen, Randomness Observed: Levels of Entropy Convergence
James P. Crutchfield, David P. Feldman
We study how the Shannon entropy of sequences produced by an information source converges to the source's entropy rate. We synthesize several phenomenological approaches to applying information...
Upper Bound on the Products of Particle Interactions in Cellular Automata
Wim Hordijk, Cosma Rohilla Shalizi, James P. Crutchfield
Particle-like objects are observed to propagate and interact in many spatially extended dynamical systems. For one of the simplest classes of such systems, one-dimensional cellular automata, we...
Cosma Rohilla Shalizi, James P. Crutchfield
Discovering relevant, but possibly hidden, variables is a key step in constructing useful and predictive theories about the natural world. This brief note explains the connections between three...
Pattern Discovery and Computational Mechanics
Cosma Rohilla Shalizi, James P. Crutchfield
Computational mechanics is a method for discovering, describing and quantifying patterns, using tools from statistical physics. It contructs optimal, minimal models of stochastic processes and their...
Resource Sharing and Coevolution in Evolving Cellular Automata
Justin Werfel, Melanie Mitchell, James P. Crutchfield
Evolving one-dimensional cellular automata (CAs) with genetic algorithms has provided insight into how improved performance on a task requiring global coordination emerges when only local...
Computational Mechanics: Pattern and Prediction, Structure and Simplicity
Cosma Rohilla Shalizi, James P. Crutchfield
Computational mechanics, an approach to structural complexity, defines a process's causal states and gives a procedure for finding them. We show that the causal-state representation--an e-machine--is...
Metastable Evolutionary Dynamics: Crossing Fitness Barriers or Escaping via Neutral Paths?
Erik Van Nimwegen, James P. Crutchfield
We analytically study the dynamics of evolving populations that exhibit metastability on the level of phenotype or fitness. In constant selective environments, such metastable behavior is caused by...
Comments on ``Simple Measure for Complexity''
James P. Crutchfield, David P. Feldman, Cosma Rohilla Shalizi
We critique the measure of complexity introduced by Shiner, Davison, and Landsberg in Ref. [1]. In particular, we point out that it is over-universal, in the sense that it has the same dependence on...
Neutral Evolution of Mutational Robustness
Eric Van Nimwegen, James P. Crutchfield, Martijn Huynen
We introduce and analyze a general model of a population evolving over a network of selectively neutral genotypes. We show that the population's limit distribution on the neutral network is solely...
The Evolutionary Unfolding of Complexity
James P. Crutchfield, Erik Van Nimwegen
We analyze the population dynamics of a broad class of fitness functions that exhibit epochal evolution|a dynamical behavior, commonly observed in both natural and artificial evolutionary processes,...
Optimizing Epochal Evolutionary Search: Population-Size Dependent Theory
Erik Van Nimwegen, James P. Crutchfield
Technological change at the firm level has commonly been modeled as random sampling from a fixed distribution o f possibilities. Such models, however, typically ignore empirically important aspects...
The Evolutionary Design of Collective Computation in Cellular Automata
James P. Crutchfield, Melanie Mitchell, Rajarshi Das
We investigate the ability of a genetic algorithm to design cellular automata that perform computations. The computational strategies of the resulting cellular automata can be understood using a...
Thermodynamic Depth of Causal States: When Paddling Around in Occam's Pool Shallowness Is a Virtue
James P. Crutchfield, Cosma Rohilla Shalizi
Thermodynamic depth is an appealing but flawed complexity measure. It depends on a set of macroscopic states for a system, but neither its original introduction by Lloyd and Pagels nor any follow-up...
Optimizing Epochal Evolutionary Search: Population-Size Independent Theory
Erik Van Nimwegen, James P. Crutchfield
Epochal dynamics, in which long periods of stasis in population fitness are punctuated by sudden innovations, is a common behavior in both natural and artificial evolutionary processes. We use a...
Mechanisms of Emergent Computation in Cellular Automata
Wim Hordijk, James P. Crutchfield, Melanie Mitchell
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....
David P. Feldman, James P. Crutchfield
We compare and contrast three different, but complementary views of "structure" and "pattern" in spatial processes. For definiteness and analytical clarity we apply all three approaches to the...
Dynamical Embodiments of Computation in Cognitive Processes
Dynamics is not enough for cognition nor is it a substitute for information processing aspects of brain behavior. Moreover, dynamics and computation are not at odds, but are quite compatible. They...
Measures of Statistical Complexity: Why?
David P. Feldman, James P. Crutchfield
We review several statistical complexity measures proposed over the last decade and a half as general indicators of structure or correlation. Recently, L\`opez-Ruiz, Mancini, and Calbet [Phys. Lett....
Quantum Automata and Quantum Grammars
Cristopher Moore, James P. Crutchfield
To study quantum computation, it might be helpful to generalize structures from language and automata theory to the quantum case. To that end, we propose quantum versions of finite-state and...
Statistical Dynamics of the Royal Road Genetic Algorithm
Erik Van Nimwegen, James P. Crutchfield, Melanie Mitchell
Genetic algorithm, statistical dynamics, royal road fitness function, metastability, evolutionary search, punctuated equilibria, fitness epoch, fitness landscape, entropy barrier, quasispecies,...
Embedded-Particle Computation in Evolved Cellular Automata
Wim Hordijk, James P. Crutchfield, Melanie Mitchell
In our work we are studying how genetic algorithms (GAs) can evolve cellular automata (CAs) to perform computations that require global coordination. The "evolving cellular automata" framework is an...
Objects that make objects: the population dynamics of structural complexity
Crutchfield, James P, Görnerup, Olof
To analyse the evolutionary emergence of structural complexity in physical processes, we introduce a general, but tractable, model of objects that interact to produce new objects. Since the...
SYNCHRONIZING TO THE ENVIRONMENT: INFORMATION-THEORETIC CONSTRAINTS ON AGENT LEARNING
JAMES P. CRUTCHFIELD, DAVID P. FELDMAN
Using an information-theoretic framework, we examine how an intelligent agent, given an accurate model of its environment, synchronizes to the environment â i.e., comes to know in which state the...
COSMA ROHILLA SHALIZI, JAMES P. CRUTCHFIELD
Discovering relevant, but possibly hidden, variables is a key step in constructing useful and predictive theories about the natural world. This brief note explains the connections between three...
DAVID P. FELDMAN, JAMES P. CRUTCHFIELD
We analyze how difficult it is to synchronize to a periodic sequence whose structure is known, when an observer is initially unaware of the sequence's phase. We examine the transient information T, a...
Finite Populations Induce Metastability in Evolutionary Search
Erik Van Nimwegen, James P. Crutchfield, Melanie Mitchell
We introduce an analytical model that predicts the dynamics of a simple evolutionary algorithm in terms of the flow in the space of fitness distributions. In the limit of infinite populations the...
Turbulent Landscapes: A Dialogue
James P. Crutchfield, Ned Kahn
From 29 June 1996 to 4 January 1997 San Francisco's Exploratorium, the noted museum of science, art, and huma perception, presents Turbulent Landscapes: The Natural Forces That Shape Our World. This...
Statistical Complexity of Simple 1D Spin Systems
James P. Crutchfield, David P. Feldman
We present exact results for two complementary measures of spatial structure generated by 1D spin systems with finite-range interactions. The first, excess entropy, measures the apparent spatial...
Computational Mechanics of Cellular Automata: An Example
James E. Hanson, James P. Crutchfield
We illustrate and extend the techniques of computational mechanics in explicating the structures that emerge in the space-time behavior of elementary one-dimensional cellular automaton rule 54. The...
Evolving Globally Synchronized Cellular Automata
Rajarshi Das, James P. Crutchfield, Melanie Mitchell, James E. Hanson
How does an evolutionary process interact with a decentralized, distributed system in order to produce globally coordinated behavior? Using a genetic algorithm (GA) to evolve cellular automata (CAs),...
Jeffrey D. Scargle, David L. Donoho, James P. Crutchfield, Thomas Steiman-Cameron, James Imamura, Karl Young
We present evidence that the quasi-periodic oscillations (QPO) and low frequency noise (LFN) characteristic of many accretion sources are different aspects of the same physical process. We analyzed a...
Quantum Automata and Quantum Grammars
Cristopher Moore, James P. Crutchfield
. To study quantum computation, it might be helpful to generalize structures from language and automata theory to the quantum case. To that end, we propose quantum versions of finite-state and...