Abstract
The observed complexity of nature is often attributed to an intrinsic propensity of matter to self-organize under certain (e.g., dissipative) conditions. In order better to understand and test this vague thesis, we define complexity as “logical depth,” a notion based on algorithmic information and computational time complexity. Informally, logical depth is the number of steps in the deductive or causal path connecting a thing with its plausible origin. We then assess the effects of dissipation, noise, and spatial and other symmetries of the initial conditions and equations of motion on the asymptotic complexity-generating abilities of statistical-mechanical model systems. We concentrate on discrete, spatially-homogeneous, locally-interacting systems such as kinetic Ising models and cellular automata.
Similar content being viewed by others
References
C. H. Bennett, inEmerging Syntheses in Science (Santa Fe Institute, Santa Fe, New Mexico, 1985), David Pines, ed., pp. 297–313. See also unpublished manuscript “On the Logical Depth of Sequences and their Reducibilities to Random Sequences” (1982). The first published description of logical depth is by G. Chaitin,I.B.M. J. Res. Develop. 21, 350–359 (1977).
C. H. Bennett and G. Grinstein,Phys. Rev. Lett. 55, 657–660 (1985).
E. Domany and W. Kinzel,Phys. Rev. Lett. 53, 311 (1985).
E. Fredkin and T. Toffoli,Internat. J. Theor. Phys. 21, 219 (1982).
P. Gacs, Technical Report No. 132, Computer Science Dept. University of Rochester, 1983, to appear inJ. Comp. Sys. Sc.
P. Gacs and J. Reif,Proceedings of the 17th ACM Symposium on the Theory of Computing, 388–395 (1985).
J. Hardy, O. de Pazzis, and Y. Pomeau,J. Math. Phys. 14, 470 (1973).
N. Margolus,Physica 10D, 81–95 (1984).
Y. Pomeau,J. Phys. 17, 12 (1984).
C. Radin,J. Math. Phys. 26, 1342 (1985).
A. L. Toom, inAdvances in Probability 6 (Multicomponent Systems), R. L. Dobrushin, ed. (Dekker, New York, 1980), pp. 549–575.
G. Vichniac,Physica 10D, 96 (1984).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Bennett, C.H. On the nature and origin of complexity in discrete, homogeneous, locally-interacting systems. Found Phys 16, 585–592 (1986). https://doi.org/10.1007/BF01886523
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01886523