# Toward a quantitative theory of self-generated complexity

@article{Grassberger1986TowardAQ, title={Toward a quantitative theory of self-generated complexity}, author={Peter Grassberger}, journal={International Journal of Theoretical Physics}, year={1986}, volume={25}, pages={907-938} }

Quantities are defined operationally which qualify as measures of complexity of patterns arising in physical situations. Their main features, distinguishing them from previously used quantities, are the following: (1) they are measuretheoretic concepts, more closely related to Shannon entropy than to computational complexity; and (2) they are observables related to ensembles of patterns, not to individual patterns. Indeed, they are essentially Shannon information needed to specify not… Expand

#### Figures from this paper

#### 592 Citations

Inferring the Dynamic, Quantifying Physical Complexity

- Computer Science
- 1989

Two approaches to the inverse problem of chaotic data analysis, estimating symbolic equations of motion and reconstructing minimal automata from chaotic data series, are reviewed. Expand

Complex systems, complexity measures, grammars and model-inferring

- Mathematics
- 1994

Abstract Quantifying complex behavior has been the subject of intense research during the last few years. In spite of these efforts there neither exists a universal measure characterizing the… Expand

Complexity through nonextensivity

- Mathematics, Physics
- 2001

The problem of defining and studying complexity of a time series has interested people for years. In the context of dynamical systems, Grassberger has suggested that a slow approach of the entropy to… Expand

The organization of intrinsic computation: complexity-entropy diagrams and the diversity of natural information processing.

- Mathematics, Physics
- Chaos
- 2008

This work uses complexity-entropy diagrams to analyze intrinsic computation in a broad array of deterministic nonlinear and linear stochastic processes, including maps of the interval, cellular automata, and Ising spin systems in one and two dimensions, Markov chains, and probabilistic minimal finite-state machines. Expand

General Remarks on Complexity

- Mathematics
- 1994

In the 1960s and 1970s it was found that nonlinear systems with only a few degrees of freedom are capable of creating a rich variety of behavior from regular to rather irregular features, later… Expand

Statistical Complexity. Applications in Electronic Systems

- Computer Science
- 2015

A statistical measure of complexity based on the interplay between the Shannon information and the separation of the set of accessible states to a system from the equiprobability distribution, i.e. the disequilibrium is introduced. Expand

Complexity of Dynamics as Variability of Predictability

- Mathematics
- 2004

We construct a complexity measure from first principles, as an average over the “obstruction against prediction” of some observable that can be chosen by the observer. Our measure evaluates the… Expand

Complexity and forecasting in dynamical systems

- 1988

We discuss ways of defining complexity in physics, and in particular for symbol sequences typically arising in autonomous dynamical systems. We stress that complexity should be distinct from… Expand

On complexity measures

- 1994

Abstract We have shown in this paper that we inevitably come to a rather general concept of complexity also in the so‐called exact sciences, such as physics or chemistry. Basing on the dualities of… Expand

Quantitative characterization of complexity and predictability

- Physics
- 1991

Abstract The asymptotic behaviour of a generic nonlinear dynamical system F is estimated by constructing a sequence of Markov models F ( l ) 0 which approach the original system increasingly better… Expand

#### References

SHOWING 1-10 OF 51 REFERENCES

Computation theory of cellular automata

- Mathematics
- 1984

Self-organizing behaviour in cellular automata is discussed as a computational process. Formal language theory is used to extend dynamical systems theory descriptions of cellular automata. The sets… Expand

TOWARD A MATHEMATICAL DEFINITION OF “ LIFE ”

- 1979

In discussions of the nature of life, the terms “complexity,” “organism,” and “information content,” are sometimes used in ways remarkably analogous to the approach of algorithmic information theory,… Expand

Algebraic properties of cellular automata

- Mathematics
- 1984

Cellular automata are discrete dynamical systems, of simple construction but complex and varied behaviour. Algebraic techniques are used to give an extensive analysis of the global properties of a… Expand

Statistical mechanics of cellular automata

- Physics
- 1983

Cellular automata are used as simple mathematical models to investigate self-organization in statistical mechanics. A detailed analysis is given of ''elementary'' cellular automata consisting of a… Expand

Ergodic theory of chaos and strange attractors

- Physics
- 1985

Physical and numerical experiments show that deterministic noise, or chaos, is ubiquitous. While a good understanding of the onset of chaos has been achieved, using as a mathematical tool the… Expand

Iterated maps on the interval as dynamical systems

- Mathematics
- 1980

Motivation and Interpretation.- One-Parameter Families of Maps.- Typical Behavior for One Map.- Parameter Dependence.- Systematics of the Stable Periods.- On the Relative Frequency of Periodic and… Expand

Introduction to Automata Theory, Languages and Computation

- Computer Science
- 1979

This book is a rigorous exposition of formal languages and models of computation, with an introduction to computational complexity, appropriate for upper-level computer science undergraduates who are comfortable with mathematical arguments. Expand

Quantitative universality for a class of nonlinear transformations

- Mathematics
- 1978

AbstractA large class of recursion relationsxn + 1 = λf(xn) exhibiting infinite bifurcation is shown to possess a rich quantitative structure essentially independent of the recursion function. The… Expand

The universal metric properties of nonlinear transformations

- Mathematics
- 1979

AbstractThe role of functional equations to describe the exact local structure of highly bifurcated attractors ofxn+1 =λf(xn) independent of a specificf is formally developed. A hierarchy of… Expand

To a mathematical definition of 'life'

- Computer Science
- SIGA
- 1970

A possible point of departure for a mathematical definition of 'life' is suggested, based on the computer, that is closely related to recent analyses of 'inductive inference' and 'randomness'. Expand