Logical depth

Bennett ([benn86], [benn88b], [bemi87b], [benn90c]) has recently introduced a measure of dynamic complexity he calls logical depth. The logical depth of an object O, denoted by is defined to be the execution time required by a universal 

Logical depth is thus consistent with our intuitive understanding of complexity. A complex biological organism is deep precisely because it requires a long and complex computation to describe. On the other hand, a regularly arranged crystal is 

---

Logical Depth Dynamic Random strings are shallow, matching intuition Hard to apply to physical systems... 

Related to Bennett s logical depth (see above), the thermodynamic depth, T) S) of a system S in state S measures how much information must be processed in order for S to evolve to S. 

The model of a molecule derived from the circle of research (Fig. 4) must be critically evaluated as to whether it contains the information associated with the emergent behaviour of the molecule. In other words, the question must be asked whether information from the atom level exceeds the logical depth necessary to understand the emergent properties of molecules as they relate to drug research (Kier and Hall, 1992). 

What is complexity There is no good general definition of complexity, though there are many. Intuitively, complexity lies somewhere between order and disorder, between regularity and randomness, between perfect crystal and gas. Complexity has been measured by logical depth, metric entropy, information content (Shannon s entropy), fluctuation complexity, and many other techniques some of them are discussed below. These measures are well suited to specific physical or chemical applications, but none describe the general features of complexity. Obviously, the lack of a definition of complexity does not prevent researchers from using the term. 

C. H. Bennett, Logical Depth and Physical Complexity, pp. 227-257 in The Universal Turing Machine A Half Century Survey (Oxford University Press, Oxford, 1988)... 

Bennett, C. H. (1988). Logical depth and physical complexity. In The universal turing machine A half-century survey (pp. 227-257). Available from http //www.springerlink.com/index/HRGl 1848P291274Q.pdf... 

Smallest Hamming weight of the heaviest row of H the logic depth of each parity or syndrome bit generator circuit usually depends on the Hamming weight of the associated row. The heaviest row determines the speed of the encoder and the decoder circuits. 

---