Логическая глубина - Logical depth - Wikipedia

Логическая глубина это мера сложность для индивидуальных струны разработан Чарльз Х. Беннетт на основе вычислительная сложность алгоритма, который может воссоздать заданный фрагмент информации. Он отличается от Колмогоровская сложность в этом он считает время вычисления алгоритма с почти минимальной длиной, а не с длиной минимального алгоритма.

Формально в контексте некоего универсального компьютера ${\displaystyle U}$ логическая глубина строки ${\displaystyle x}$ до уровня значимости ${\displaystyle s}$ дан кем-то ${\displaystyle {\text{min}}\{T(p):(|p|-|p^{*}|<s)\wedge (U(p)=x)\},}$ время работы самой быстрой программы, которая производит ${\displaystyle x}$ и не более чем ${\displaystyle s}$ дольше минимальной программы.

Смотрите также

• Эффективная сложность
• Самостоятельная непохожесть
• Сложность прогнозирования
• Изысканность (теория сложности)

Рекомендации

• Беннет, Чарльз Х. (1988), «Логическая глубина и физическая сложность», в Herken, Rolf (ed.), Универсальная машина Тьюринга: обзор за полвека, Oxford U. Press, стр. 227–257, CiteSeerX  10.1.1.70.4331
• Крейг, Эдвард (1998), «Вычислимость и информация, Раздел 6: Логическая глубина», Энциклопедия философии Рутледж, Vol. 10: Указатель, Тейлор и Фрэнсис, стр. 481, ISBN  9780415073103