“A complex system is a system that has a largely incompressible regularity,” says evolutionary theorist David Krakauer (~56:30), at this August 2012 Santa Fe Institute discussion.
Physicist Murray Gell-Mann adds (~1:11:00), “The minimum description length of the regularities is the complexity.” And computer scientist Melanie Mitchell notes the multiple definitions of complexity (~55:45).
This video with Krakauer, Gell-Mann, Mitchell, theoretical physicist Christopher Llewellyn Smith, and archaeologist Colin Renfrew is one of many available from SFI.
From “Complexity: Life, Scale, & Civilization”:
Something is simple if it can be written down in some known notation and take up very little space — minimum description length. So if we already have a certain kind of mathematics for one skin of the onion, and something like it describes the next level of the onion, and something very close to that describes the level after, then we have something that looks beautiful to us. Because we’re employing mathematics that we already know.
And that seems to be the case. It seems to be the case that the fundamental law of elementary particle physics — and probably the initial condition of the universe, as well — that both of them are very simple, in this sense. The skins of the onion resemble one another. That gives us a remarkable power, and you can see this over and over again.
Accidents, as we’re describing them, lead to new regularities. … All living things on earth have a DNA- or RNA-based genome. The original circumstances that gave rise to that were probably very hard, if not impossible, to predict. But once that was there, a huge number of new regularities emerged — a new layer of the onion.