La complejidad de Kolmogorov de una cadena s es igual a la longitud del programa más corto que calcula s y se detiene. Mide la falta de estructura en una cuerda.
Arreglemos una codificación sin prefijo de máquinas de Turing y una máquina universal de Turing que en la entrada (codificada como el código sin prefijo de seguido de ) emite salidas de en la entrada (posiblemente ambos corriendo para siempre). Defina la complejidad de Kolmogorov de , , como la...
La complejidad del prefijo de Kolmogorov (es decir, K(x)K(x)K(x) es el tamaño del programa mínimo de auto delimitación que genera xxx ) tiene varias características agradables: Corresponde a una intuición de dar cadenas con patrones o estructura de menor complejidad que las cadenas sin ellas. Que...
Digamos que tenemos un problema de cálculo, por ejemplo, 3-SAT, que tiene un conjunto de instancias de problemas (posibles entradas) . Normalmente en el análisis de algoritmos o teoría de la complejidad computacional, tenemos algunos conjuntos de todas las entradas de longitud , y una función que...
Considere el siguiente razonamiento: Deje que denote la complejidad de Kolmogorov de la cadena x . El teorema de incompletitud de Chaitin dice queK( x )K(x)K(x)Xxx para cualquier sistema coherente y suficientemente fuerte formales , existe una constante T (dependiendo sólo del sistema formal y...
Muchos teoremas y "paradojas": la diagonalización de Cantor, la indecidibilidad de la incubación, la indecisión de la complejidad de Kolmogorov, la incompletitud de Gödel, la incompletitud de Chaitin, la paradoja de Russell, etc., tienen esencialmente la misma prueba por diagonalización (tenga en...
Supongamos que denota la complejidad de Kolmogorov de una cadena x . ¿Existe una cadena tal que K ( x x ) < K ( x ) . (Aquí x x es la concatenación de x consigo mismo). Aquí se hizo una pregunta similar pero diferente , pero el contraejemplo dado en la respuesta a esa pregunta no funciona para...
Incompleto de Chaitin teorema dice que no lo suficientemente fuerte como la teoría de la aritmética puede llegar K(s)>LK(s)>LK(s) > L , donde K(s)K(s)K(s) es la complejidad de Kolmogorov de cuerda sss y LLL es una constante suficientemente grande. LLL es suficientemente grande si es más...
Por lo general, la entropía de Shannon se usa para probar los resultados de la codificación del canal. Incluso para los resultados de separación del canal fuente se utiliza la entropía de shannon. Dada la equivalencia entre las nociones de información de Shannon (global) frente a Kolmogorov...
Podemos pensar en la complejidad de Kolmogorov de una cadena xxx como la longitud del programa más corto PPPy la entrada yyy tal que x=P(y)x=P(y)x = P(y) . Por lo general, estos programas se extraen de un conjunto completo de Turing (como PPP podría ser la descripción de una máquina de Turing, o...
La motivación para esta pregunta es el hecho de que la mayoría de las cadenas de n bits son incompresibles. Intuitivamente, podemos proponer por analogía que la mayoría de las pruebas para tautologías son incompresibles para el tamaño polinómico. Básicamente, mi intuición es que algunas pruebas son...
Para responder "qué problemas se pueden resolver con la informática", desarrollamos la teoría de la computabilidad. Para los problemas que son computables, ¿existe una teoría para responder la pregunta "¿Es el programa el que obtengo más simple"? No creo que la complejidad computacional responda...
Los generadores invulnerables se definen de la siguiente manera: Sea una relación NP y M una máquina que acepte L ( R ) . Informalmente, un programa es un generador invulnerable si, en la entrada 1 n , produce pares de instancia-testigo ( x , w ) ∈ R , con | x | = n , de acuerdo con una...
La complejidad de Kolmogorov de una cadena no es computable. Sin embargo, en un subconjunto aleatorio de tamaño de cadenas binarias de longitud , el número se espera que tengan menos de complejidad algún entero menor que (en función de , y )?METROMMnortennnorte0
Arreglemos una codificación de máquinas de Turing y una máquina universal de Turing, U, que en la entrada (T, x) emite cualquier salida de T en la entrada x (posiblemente ambas funcionando para siempre). Defina la complejidad de Kolmogorov de x, K (x), como la longitud del programa más corto, p, de...
Estoy buscando una prueba de que la complejidad de Kolmogorov es indiscutible utilizando una reducción de otro problema incontestable. La prueba común es una formalización de la paradoja de Berry en lugar de una reducción, pero debe haber una prueba reduciendo algo como el Problema de detención o...
¿Cuáles son las aplicaciones de la complejidad de Kolmogorov en la teoría de números y en los campos relacionados con las pruebas? (La monografía de Li & Vitanyi no tiene muchas aplicaciones relacionadas con la teoría de números). Una de las buenas pruebas que he encontrado es la prueba de la...
Para las complejidades de Kolmogorov inducida por lenguajes de descripción esencialmente óptimos, ¿existe un entero c tal que para todos los enteros positivos n , exista una cadena x tal queKK\hspace{.02 in}KCccnnnxxxn<K(x)<n+cn<K(x)<n+c\;\;\; n \: < \: K(x) \: < \: n\hspace{-0.04...