Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

The past several decades has seen a considerable effort toward the development of measures of complexity. These measures are intended to capture, to varying degrees, our intuitive notions of pattern, regularity, memory, or structure. One of the questions motivating this work concerns the nature of the relationship between complexity and entropy. Is complexity the absence of disorder? Are maximally complex phenomena those that combine order and disorder? Is there a general relationship between complexity and entropy? These questions are often addressed by appealing to a complexity-entropy diagram: a plot of a system's complexity vs. its entropy. In this talk I will review several information-theoretic measures of randomness and structural complexity. I will then present calculations of complexity-entropy diagrams for a range of systems: one-dimensional maps of the unit interval; one- and two-dimensional Ising models; Markov chains; cellular automata; and topological languages. The main conclusion that will emerge from this survey is that there is a large range of possible complexity-entropy behaviors. In particular, there is not a universal complexity-entropy curve.