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

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

Формально в контексте некоего универсального компьютера логическая глубина строки до уровня значимости дан кем-то время работы самой быстрой программы, которая производит и не более чем дольше минимальной программы.

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

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

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