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. Charles H. Bennett. 1995. In , edited by Rolf Herken, 2:207–35. Springer Vienna. DOI.