zbMATH — the first resource for mathematics

The calculi of emergence: Computation, dynamics and induction. (English) Zbl 0860.68046
Summary: 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 terms of how modelbuilding observers infer from measurements the computational capabilities embedded in nonlinear processes. An observer’s notion of what is ordered, what is random, and what is complex in its environment depends directly on its computational resources: the amount of raw measurement data, of memory, and of time available for estimation and inference. The discovery of structure in an environment depends more critically and subtlety though on how those resources are organized. The descriptive power of the observer’s chosen (or implicit) computational model class, for example, can be an overwhelming determinant in finding regularity in data.
This paper presents an overview of an inductive framework – hierarchical \(\varepsilon\)-machine reconstruction – in which the emergence of complexity is associated with the innovation of new computational model classes. Complexity metrics for detecting structure and quantifying emergence, along with an analysis of the constraints on the dynamics of innovation, are outlined. Illustrative examples are drawn from the onset of unpredictability in nonlinear systems, finitary nondeterministic processes, and cellular automata pattern recognition. They demonstrate how finite inference resources drive the innovation of new structures and so lead to the emergence of complexity.

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q99 Theory of computing
68Q80 Cellular automata (computational aspects)
94A17 Measures of information, entropy
68T10 Pattern recognition, speech recognition
Full Text: DOI
[1] Whitehead, A.N., Process and reality, (1978), The Free Press New York, corrected edition
[2] Reynolds, C.W., Flocks, herds, and schools: A distributed behavioral model, Computer graphics, 21, 25-34, (1987)
[3] Holldobler, B.; Wilson, E.O., The ants, ()
[4] Fama, E.F., Efficient capital markets II, J. finance, 46, 1575-1617, (1991)
[5] Land, E., The retinex, Am. scientist, 52, 247-264, (1964)
[6] Wandell, B.A., Color appearance: the effects of illumination and spatial patterns, (), 2458-2470
[7] Kovacs, I.; Julesz, B., A closed curve is much more than an incomplete one-effect of closure in figure ground segmentation, (), 7495-7497
[8] Crutchfield, J.P.; Packard, N.H.; Farmer, J.D.; Shaw, R.S., Chaos, sci. am., 255, 46-57, (1986)
[9] ()
[10] Turing, A.M., The chemical basis of morphogenesis, Trans. roy. soc. ser. B, 237, 5, (1952)
[11] Winfree, A.T., The geometry of biological time, (1980), Springer Berlin · Zbl 0856.92002
[12] Ouyang, Q.; Swinney, H.L., Transition from a uniform state to hexagonal and striped Turing patterns, Nature, 352, 610-612, (1991)
[13] Stanley, H.E., Introduction to phase transitions and critical phenomena, (1971), Oxford Univ. Press Oxford
[14] Bak, P.; Chen, K., Self-organized criticality, Physica A, 163, 403-409, (1990)
[15] Binney, J.J.; Dowrick, N.J.; Fisher, A.J.; Newman, M.E.J., The theory of critical phenomena, (1992), Oxford Univ. Press Oxford · Zbl 0771.00009
[16] Thompson, D.W., On growth and form, (1917), Cambridge Univ. Press Cambridge
[17] Meinhardt, H., Models of biological pattern formation, (1982), Academic Press London
[18] Forrest, S., Emergent computation: self-organizing, collective, and cooperative behavior in natural and artificial computing networks: introduction to the proceeding of the ninth annual CNLS conference, (), 1-11
[19] Kemeny, J.G., The use of simplicity in induction, Phil. rev., 62, 391, (1953)
[20] Wallace, C.S.; Boulton, D.M., An information measure for classification, Comput. J., 11, 185, (1968) · Zbl 0164.46208
[21] Rissanen, J., Modeling by shortest data description, Automatica, 14, 462, (1978) · Zbl 0418.93079
[22] Crutchfield, J.P.; McNamara, B.S., Equations of motion from a data series, Complex systems, 1, 417-452, (1987) · Zbl 0675.58026
[23] Rissanen, J., Stochastic complexity in statistical inquiry, (1989), World Scientific Singapore · Zbl 0800.68508
[24] Crutchfield, J.P.; Young, K., Inferring statistical complexity, Phys. rev. lett., 63, 105-108, (1989)
[25] Wolfram, S., Computation theory of cellular automata, Comm. math. phys., 96, 15, (1984) · Zbl 0587.68050
[26] Blum, L.; Shub, M.; Smale, S., On a theory of computation over the real numbers, Bull. AMS, 21, 1, (1989)
[27] Nordahl, M.G., Formal languages and finite cellular automata, Complex systems, 3, 63, (1989) · Zbl 0734.68067
[28] Hanson, J.E.; Crutchfield, J.P., The attractor-basin portrait of a cellular automaton, J. stat. phys., 66, 1415, (1992) · Zbl 0892.58051
[29] Crutchfield, J.P., Unreconstructible at any radius, Phys. lett. A, 171, 52-60, (1992)
[30] Moore, C., Real-valued, continuous-time computers: A model of analog computation, part I, Technical report 93-04-018, (1993), Santa Fe Institute
[31] Hopcroft, J.E.; Ullman, J.D., Introduction to automata theory, languages, and computation, () · Zbl 0196.01701
[32] Lewis, H.R.; Papadimitriou, C.H., Elements of the theory of computation, () · Zbl 0464.68001
[33] Brookshear, J.G., Theory of computation: formal languages, automata, and complexity, () · Zbl 0678.68001
[34] Crutchfield, J.P., Semantics and thermodynamics, (), 317-359
[35] Aho, A.V., Indexed grammars-an extension of context-free grammars, J. assoc. comp. Mach., 15, 647, (1968) · Zbl 0175.27801
[36] Aho, A.V., Nested stack automata, J. assoc. comp. Mach., 16, 383, (1969) · Zbl 0184.28603
[37] Weiss, B., Subshifts of finite type and sofic systems, Monastsh. math., 77, 462, (1973) · Zbl 0285.28021
[38] Walker, A., Adult languages of L systems and the chomsky hierarchy, (), 201
[39] Lindenmayer, A.; Prusinkiewicz, P., Developmental models of multicellular organisms: A computer graphics perspective, (), 221
[40] ()
[41] Allevi, E.; Cherubini, A.; Crespi-Reghizzi, S., Breadth-first context-free grammars and queue automata, Lect. notes in comp. sci., 324, 162, (1988) · Zbl 0652.68094
[42] Cherubini, A.; Citrini, C.; Crespi-Reghizzi, S.; Mandrioli, D., Quasi-real-time FIFO automata, breadth first grammars, and their relations, Theo. comp. sci., 85, 171-203, (1991) · Zbl 0745.68069
[43] Rogers, H., Theory of recursive functions and effective computability, (1967), McGraw-Hill New York · Zbl 0183.01401
[44] Searls, D.B., The linguistics of DNA, Am. sci., 80, 579-591, (1992)
[45] Chaitin, G., On the length of programs for computing finite binary sequences, J. ACM, 13, 145, (1966) · Zbl 0187.28303
[46] Kolmogorov, A.N., Three approaches to the concept of the amount of information, Prob. info. trans., 1, 1, (1965)
[47] Solomonoff, R.J., A formal theory of inductive control, Info. control, 7, 224, (1964) · Zbl 0259.68038
[48] Shannon, C.E.; Weaver, W., The mathematical theory of communication, (1962), Univ. of Illinois Press Champaign-Urbana
[49] Brudno, A.A., Entropy and the complexity of the trajectories of a dynamical system, Trans. Moscow math. soc., 44, 127, (1983) · Zbl 0532.28019
[50] Ford, J., How random is a coin toss?, Physics today, (April 1983)
[51] Bennett, C.H., Dissipation, information, computational complexity, and the definition of organization, ()
[52] Crutchfield, J.P.; Packard, N.H., Symbolic dynamics of noisy chaos, Physica D, 7, 201-223, (1983)
[53] Shaw, R., The dripping faucet as a model chaotic system, (1984), Aerial Press Santa Cruz, CA
[54] Grassberger, P., Toward a quantitative theory of self-generated complexity, Int. J. theo. phys., 25, 907, (1986) · Zbl 0605.94003
[55] Angluin, D.; Smith, C.H., Inductive inference: theory and methods, Comp. surveys, 15, 237, (1983)
[56] Crutchfield, J.P.; Young, K., Computation at the onset of chaos, (), 233-269
[57] Crutchfield, J.P., Knowledge and meaning … chaos and complexity, (), 66-101
[58] Crutchfield, J.P., Reconstructing language hierarchies, (), 45
[59] J.P. Crutchfield and D.R. Upper, in preparation.
[60] Crutchfield, J.P.; Hanson, J.E., Turbulent pattern bases for cellular automata, Physica D, 69, 279-301, (1993) · Zbl 0794.68111
[61] Feigenbaum, M.J., Universal behavior in nonlinear systems, Physica D, 7, 16, (1983) · Zbl 0533.58025
[62] Kadanoff, L.P.; Feigenbaum, M.J.; Shenker, S.J., Quasiperiodicity in dissipative systems: a renormalization group analysis, Physica D, 5, 370, (1982)
[63] Crutchfield, J.P., Observing complexity and the complexity of observation, (), 235-272
[64] Blackwell, D.; Koopmans, L., On the identifiability problem for functions of Markov chains, Ann. math. statist., 28, 1011, (1957) · Zbl 0080.34901
[65] Ito, H.; Amari, S.-I.; Kobayashi, K., Identifiability of hidden Markov information sources and their minimum degrees of freedom, IEEE info. th., 38, 324, (1992) · Zbl 0742.60041
[66] Crutchfield, J.P.; Hanson, J.E., Attractor vicinity decay for a cellular automaton, Chaos, 3, 2, 215-224, (1993) · Zbl 1055.37508
[67] Hanson, J.E., Computational mechanics of cellular automata, (), University of California, Berkeley, 1993
[68] Boccara, N.; Nasser, J.; Roger, M., Particle-like structures and their interactions in spatio-temporal patterns generated by one-dimensional deterministic cellular automaton rules, Phys. rev. A, 44, 866-875, (1991)
[69] Russell, B., A history of western philosophy, (1945), Simon and Schuster New York
[70] Kuhn, T.S., The structure of scientific revolutions, (1962), University of Chicago Press Chicago
[71] Langton, C.G., Computation at the edge of chaos: phase transitions and emergent computation, (), 12
[72] Packard, N.H., Adaptation toward the edge of chaos, (), 293-301
[73] Kauffman, S.A., Origins of order: self-organization and selection in evolution, (1993), Oxford Univ. Press New York
[74] Mitchell, M.; Hraber, P.; Crutchfield, J.P., Revisiting the edge of chaos: evolving cellular automata to perform computations, Complex systems, 7, 89-130, (1993) · Zbl 0834.68086
[75] Maynard-Smith, J., Evolutionary genetics, (1989), Oxford Univ. Press Oxford
[76] Monod, J., Chance and necessity: an essay on the natural philosophy of modern biology, (1971), Vintage Books New York
[77] Gould, S.J., Wonderful life, (1989), Norton New York
[78] Waddington, C.H., The strategy of the genes, (1957), Allen and Unwin
[79] Goodwin, B., Evolution and the generative order, (), 89-100
[80] Fontana, W.; Buss, L., What would be conserved if the tape were played twice?, (), 757-761
[81] Fontana, W.; Buss, L., The arrival of the fittest: toward a theory of biological organization, Bull. math. bio., 56, 1-64, (1994) · Zbl 0798.92021
[82] ()
[83] ()
[84] Holland, J.H., Adaptation in natural and artificial systems, (1992), MIT Press Cambridge, MA
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.