James P. Crutchfield

Inferring Markov Chains: Bayesian Estimation, Model Comparison, Entropy Rate, and Out-of-class Modeling (2007)

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...

Insects, Trees, and Climate: The Bioacoustic Ecology of Deforestation and Entomogenic Climate Change (2006)

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)

How Random is a Coin Toss? Bayesian Inference and the Symbolic Dynamics of Deterministic Chaos (2006)

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)

Computation in Finitary Stochastic and Quantum Processes (2006)

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...

Hierarchical Self-Organization in the Finitary Process Soup (2006)

We introduce stochastic and quantum finite-state transducers as computation-theoretic models of classical stochastic and quantum finitary processes. Formal process languages, representing the...

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)

Crutchfield, James P.

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...

Automated Pattern Detection--An Algorithm for Constructing Optimally Synchronizing Multi-Regular Language Filters (2004)

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...

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...

Synchronizing to Periodicity: The Transient Information and Synchronization Time of Periodic Sequences (2002)

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...

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...

Information Bottlenecks, Causal States, and Statistical Relevance Bases: How to Represent Relevant Information in Memoryless Transduction (2000)

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...

The Evolutionary Unfolding of Complexity (2000)

Embedded-Particle Computation in Evolved Cellular Automata (2000)

. 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...

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...

Dynamics, Computation, and the "Edge of Chaos": A Re-Examination (2000)

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]...

Evolving Cellular Automata with Genetic Algorithms: A Review of Recent Work (2000)

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...

Erik van Nimwegen, (2000)

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...

Evolving Globally Synchronized Cellular Automata (2000)

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),...

Mechanisms of Emergent Computation in Cellular Automata (2000)

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 Evolution of Emergent Computation (2000)

James P. Crutchfield, Melanie Mitchell

This paper reports the application of new methods for detecting computation in nonlinear processes to a simple evolutionary model that allows us to directly address these questions. The main result...

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 (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)

. 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...

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...

. 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...

. 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...