Logical depth

tags
Complexity metrics
references
(Bennett 1995)

Logical depth can be defined as the run time of the Turing Machine that uses the minimal representation for an input \(x\), \(M_{\min}(x)\) — which is also its Kolmogorov complexity . It is therefore uncomputable (because the minimal representation is uncomputable).

Bibliography

  1. . . "Logical Depth and Physical Complexity". In The Universal Turing Machine A Half-century Survey, edited by Rolf Herken, 2:207–35. Vienna: Springer Vienna. DOI.

Links to this note

Last changed | authored by

Comments


← Back to Notes