We have discussed several different measures of static complexity, which measure ratherdifferent things. But all these measures have one thing in common: they work by singling out theone pattern which minimizes some quantity. It is equally interesting to study the total amount of structure in an entity. For instance, suppose x and x% both…

   Koppel [8] has recently proposed an alternative to the KCS complexity measure. According toKoppel’s measure, the sequences which are most complex are not the structureless ones. Neither,of course, are they the ones with very simple structures, like 00000000000…. Rather, the morecomplex sequences are the ones with more "sophisticated" structures.The basic idea [10] is that…

   Charles S. Peirce, the turn-of-the-century American philosopher, liked to talk about the "onelaw of mind." He gave this law many different formulations, the most suggestive of which wasonly five words: "the tendency to take habits". This simple, potent idea is at the heart of thetheory of mind to be presented in the following chapters.…

   It is natural to define a random sequence as one which has no statistical regularities (vonMises, 1957). For instance, one might propose that in a random binary sequence 1 should occurexactly as often as 0. Also, one might require that the four doublets 00, 01, 10 and 11 shouldoccur equally often. And perhaps the…

   What does it mean to say that one thing is more complex than another? Like most words,"complexity" has many meanings. In Chapter 1 we briefly discussed the "complexity" ofcomputation — of problems and algorithms. In this chapter we will consider several approachesto quantifying the complexity of individual entities, beginning with the simple Kolmogorov-Chaitin-Solomonoff definition.  …