Profundidad lógica - Enciclopedia

La profundidad lógica es una medida de complejidad para cadenas individuales ideada por Charles H. Bennett basada en la complejidad computacional de un algoritmo que puede recrear una pieza de información dada. Diferencia de la complejidad de Kolmogorov en que considera el tiempo de cómputo del algoritmo con longitud casi mínima, en lugar de la longitud del algoritmo mínimo.

Informalmente, la profundidad lógica de una cadena


x


{\displaystyle x}

a un nivel de significación


s


{\displaystyle s}

es el tiempo requerido para calcular


x


{\displaystyle x}

por un programa no mayor de


s


{\displaystyle s}

bits más largo que el programa más corto que calcula


x


{\displaystyle x}

.

Formalmente, dejemos que



p

∗




{\displaystyle p^{*}}

sea el programa más corto que calcula una cadena


x


{\displaystyle x}

en algún ordenador universal


U


{\displaystyle U}

. Entonces, la profundidad lógica de


x


{\displaystyle x}

a un nivel de significación


s


{\displaystyle s}

se da por



min

{
T
(
p
)
:
(

|

p

|

−

|


p

∗



|

<
s
)
∧
(
U
(
p
)
=
x
)
}
,


{\displaystyle {\text{min}}\{T(p):(|p|-|p^{*}|<s)\wedge (U(p)=x)\},}

donde


T
(
p
)


{\displaystyle T(p)}

es el número de pasos de cómputo que


p


{\displaystyle p}

realiza en


U


{\displaystyle U}

para producir


x


{\displaystyle x}

y detenerse.


Véase también
Complejidad efectiva
Autodissimilitud
Predicción de complejidad
Sophistication (teoría de la complejidad)


Referencias

Bennett, Charles H. (1988), "Logical Depth and Physical Complexity", en Herken, Rolf (ed.), The Universal Turing Machine: a Half-Century Survey, Oxford U. Press, pp. 227–257, CiteSeerX 10.1.1.70.4331
Craig, Edward (1998), "Computability and Information, Section 6: Logical Depth", Routledge Encyclopedia of Philosophy, Vol. 10: Index, Taylor & Francis, p. 481, ISBN 9780415073103