Logical depth

Logical depth is a measure of complexity devised by Charles H. Bennett based on the computational complexity of an algorithm that can recreate a given piece of information. It differs from Kolmogorov complexity in that it considers the computation time of the algorithm with the shortest length, rather than its length.

See also

• Effective complexity
• Self-dissimilarity
• Forecasting complexity
• Sophistication (complexity theory)

References

• Bennett, Charles H. (1988), "Logical Depth and Physical Complexity", in Herken, Rolf (ed.), The Universal Turing Machine: a Half-Century Survey, Oxford U. Press, pp. 227–257, CiteSeerX 10.1.1.70.4331
• Craig, Edward (1998), "Computability and Information, Section 6: Logical depth", Routledge Encyclopedia of Philosophy, Vol. 10: Index, Taylor & Francis, p. 481, ISBN 9780415073103
• Mitchell, Melanie (2009), "Complexity as Logical Depth", Complexity: A Guided Tour, Oxford University Press, pp. 100–101, ISBN 9780199741021