Logická hloubka - Logical depth - Wikipedia

Logická hloubka je měřítkem složitost pro jednotlivce struny vymyslel Charles H. Bennett založeno na výpočetní složitost algoritmu, který dokáže znovu vytvořit danou informaci. Liší se od Kolmogorovova složitost v tom smyslu, že výpočetní čas spíše než s délkou minimálního algoritmu.

Formálně v kontextu nějakého univerzálního počítače ${ displaystyle U}$ logická hloubka řetězce ${ displaystyle x}$ na úroveň významnosti ${ displaystyle s}$ darováno ${ displaystyle { text {min}} {T (p) :( | p | - | p ^ {*} |$ doba chodu nejrychlejšího programu, který produkuje ${ displaystyle x}$ a není víc než ${ displaystyle s}$ delší než minimální program.

Viz také

• Efektivní složitost
• Sebe nepodobnost
• Složitost prognóz
• Sofistikovanost (teorie složitosti)

Reference

• Bennett, Charles H. (1988), „Logical Depth and Physical Complexity“, Herken, Rolf (ed.), The Universal Turing Machine: a Half-Century Survey, Oxford U. Press, s. 227–257, CiteSeerX  10.1.1.70.4331
• Craig, Edward (1998), „Vyčíslitelnost a informace, část 6: Logická hloubka“, Routledge Encyclopedia of Philosophy, sv. 10: Rejstřík, Taylor & Francis, s. 481, ISBN  9780415073103