Logical depth

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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[edit]

References[edit]

  • Bennett, Charles H. (1988), "Logical Depth and Physical Complexity", in Herken, Rolf, 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