×

An algebraic measure of complexity. (English) Zbl 0719.58021

The notion of an algebraic measure of complexity is discussed: Given a discrete dynamical system U: \(S\to S\), where S is the set of states, a reading operator \(\sigma\) acting on S is introduced which determines which state aspects are observable and this generates a group (\(\sigma\)). State configurations are thus defined as sets of states that cannot be resolved by \(\sigma\). The set of configurations is ordered in complexity layers, defined as classes of configurations that are stabilized by isomorphic subgroups of (\(\sigma\)). These layers are indexed by (\(\sigma\))/H where H, up to an isomorphism, stabilizes the configuration of a given layer. The algebraic complexity is given as (\(\sigma\))/H and for finite (\(\sigma\)) a complexity number is introduced. The notions of complexity degradation and translation complexity are discussed with particular reference to one-dimensional cellular automata.
Reviewer: R.Cowen (Gaborone)

MSC:

37B99 Topological dynamics
Full Text: DOI

References:

[1] Wolfram, S., Undecidability and intractability in theoretical physics, Phys. Rev. Lett., 54, 735 (1985), and references therein
[2] Wolfram, S., Theory and Applications of Cellular Automata (1986), World Scientific: World Scientific Singapore
[3] Physica D, 10, 182 (1984)
[4] Bai-Lin, Hao, Chaos (1984), World Scientific: World Scientific Singapore · Zbl 0559.58012
[5] von Neumann, J., (Burks, A. W., Theory of Self-Reproducing Automata (1966), Univ. of Illinois Press: Univ. of Illinois Press Urbana, IL)
[6] Lloyd, S.; Pagels, H., Ann. of Phys., 188, 186 (1988)
[7] Grassberger, P., Randomness, information and complexity, (Proceedings of the ’89 Mexican School of Statistical Physics (1990), SMF: SMF Mexico) · Zbl 1185.94097
[8] Waddington, C. H., Tools for Thought (1977), Paladin: Paladin London
[9] Kolmogorov, A. N., Three approaches to the quantitative definition of information, Probl. Inform. Theory, 1, 3 (1965) · Zbl 0271.94018
[10] Wolfram, S., Computational theory of cellular automata, Commun. Math. Phys., 96, 15 (1984) · Zbl 0587.68050
[11] Bennett, C. H., (Pines, D., Emerging Syntheses in Science (1985))
[12] Huberman, B. A.; Hogg, T., Complexity and adaption, Physica D, 22, 376 (1986)
[13] Hopcroft, J.; Ullman, J., Introduction to Automata Theory, Languages and Computations (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0426.68001
[14] Wolfram, S., Statistical mechanics of cellular automata, Rev. Mod. Phys., 55, 601 (1983) · Zbl 1174.82319
[15] Liu, C. L., Introduction to Combinatorial Mathematics (1968), Mc Graw-Hill: Mc Graw-Hill New York, chapter 5 · Zbl 0188.03801
[16] Vinogradov, I. M., Elements of Number Theory (1954), Dover: Dover New York · Zbl 0057.28201
[17] Metropolis, N.; Stein, M. L.; Stein, P. R., On finite limit sets for transformations on the unit interval, J. Comb. Theory, 15, 25 (1973) · Zbl 0259.26003
[18] May, R. M., Simple mathematical models with very complicated dynamics, Nature, 261, 459 (1976) · Zbl 1369.37088
[19] Urías, J., Complex Systems (1990), submitted for publication
[20] Urías, J., One-dimensional cellular automata as arithmetic recursions, Physica D, 36, 109 (1989) · Zbl 0684.68076
[21] Hortensius, P. D.; Card, H. C.; McLeod, R. D.; Pries, W., Importance sampling for Ising computers using one-dimensional cellular automata, IEEE Trans. Comput., 38, 769 (1989)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.