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

Bennett, Charles H. 1995. “Logical Depth and Physical Complexity.” In The Universal Turing Machine a Half-Century Survey, edited by Rolf Herken and Rolf Herken, 2:207–35. Vienna: Springer Vienna.


← Back to Notes