### Computation at the Onset of Chaos

James P. Crutchfield and Karl Young

Physics Department

University of California

Berkeley, California 94720, USA

**ABSTRACT: **Computation at levels beyond storage and transmission of information
appears in physical systems at phase transitions. We investigate this
phenomenon using minimal computational models of dynamical systems
that undergo a transition to chaos as a function of a nonlinearity
parameter. For period-doubling and band-merging cascades, we derive
expressions for the entropy, the interdependence of epsilon-machine
complexity and entropy, and the latent complexity of the transition to
chaos. At the transition deterministic finite automaton models diverge in
size. Although there is no regular or context-free Chomsky grammar in this
case, we give finite descriptions at the higher computational level of
context-free Lindenmayer systems. We construct a restricted indexed
context-free grammar and its associated one-way nondeterministic nested
stack automaton for the cascade limit language.

This analysis of a family of dynamical systems suggests a complexity
theoretic description of phase transitions based on the informational
diversity and computational complexity of observed data that is
independent of particular system control parameters. The approach gives
a much more refined picture of the architecture of critical states than
is available via correlation functions, mutual information, and
statistical mechanics generally. The analytic methods establish
quantitatively the longstanding observation that significant computation
is associated with the critical states found at the border between order
and chaos.

J. P. Crutchfield and K. Young, "Computation at the Onset of Chaos",
in **Entropy, Complexity, and the Physics of Information**,
W. Zurek, editor, SFI Studies in the Sciences of Complexity,
**VIII**, Addison-Wesley, Reading, Massachusetts (1990) 223-269.
[ps]= ??kb
[pdf]= 575kb
[ps.gz]= 297kb.

*Note: Some figures are not included in these electronic versions.
See original publication.*