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 longitud del programa más corto tal que .U ( T , x ) T x T x x K ( x ) p U ( p ) = x
¿Existe una máquina Turing tal que por cada entrada produzca un número enteroeso es diferente de la complejidad de Kolmogorov de , es decir, pero ?T x T ( x ) ≤ | x | x T ( x ) ≠ K ( x ) lim inf | x | → ∞ T ( x ) = ∞
T x T(x)≤|x| x T(x)≠K(x) lim inf|x|→∞T(x)=∞
Las condiciones son necesarias porque
(a) si, entonces sería fácil generar un número que es trivialmente diferente de K (x) porque es mayor que | x | + c_U ,T ( x ) ≰ | x | K ( x ) | x | + c U
(b) si lim inf | x | → ∞ T ( x ) < C
También tenga en cuenta que nuestro trabajo sería fácil si sabemos que T ( x )
Sé que las relaciones se estudian mucho en general, pero
¿Alguien ha hecho alguna vez una pregunta similar donde nuestro objetivo es dar un algoritmo que no genera algún parámetro?
Mi motivación es este problema http://arxiv.org/abs/1302.1109 .
Respuestas:
La pregunta puede reformularse como si lim inf | x | → ∞ | T ( x ) - K ( x ) | = 0 , y como Denis señala en los comentarios, esto es falso para algunas codificaciones. Aquí hay una declaración más débil y un intento de prueba que no depende de ningún detalle de la codificación, pero supondré un lenguaje binario por simplicidad:liminf|x|→∞|T(x)−K(x)|=0
Sea T : { 0 , 1 } ∗ → N una función computable que satisfaga 0 ≤ T ( x ) ≤ | x | y lim inf | x | → ∞ T ( x ) = ∞ . Entonces lim inf | x | → ∞ | T ( x ) - K ( x ) | < ∞T:{0,1}∗→N 0≤T(x)≤|x| liminf|x|→∞T(x)=∞ liminf|x|→∞|T(x)−K(x)|<∞ . Informalmente, si hay un objetivo alrededor de la complejidad de Kolmogorov de cada cadena que crece sin límites, ninguna función computable puede evitar golpearlo.
Para ver esto, dejar que n ser un aleatorio b número bits, es decir, 0 ≤ n < 2 b y K ( n ) ≥ b . Para todo b existe una n aleatoria de este tipo También tenga en cuenta que hay un número infinito de valores de b para los cuales | { T ( x ) = b } | ≥ 2 b , esto se desprende de las condiciones impuestas en T . Ahora vamos x ser el n ºn b 0≤n<2b K(n)≥b b n b |{T(x)=b}|≥2b T x nth cadena más pequeña tal que T ( x ) = b . Es evidente que hay una constante c 1 tal que K ( x ) > b - c 1 , porque K ( n ) ≥ b y n puede calcularse a partir x . Y hay una constante c 2 tal que K ( x ) < b + c 2 , porque K ( n )T(x)=b c1 K(x)>b−c1 K(n)≥b n x c2 K(x)<b+c2 K(n) también está limitado desde arriba solo por una constante más que b , y x puede calcularse a partir de n . Entonces | K ( x ) - T ( x ) | < c 1 + c 2 , y tenemos un número infinito de opciones para b (aquellas con una preimagen de cardinalidad de al menos 2 b ), produciendo un número infinito de valores para x , así que hemos terminado.b x n |K(x)−T(x)|<c1+c2 b 2b x
Una implicación es que para algunos c ∈ Z , T ( x ) = K ( x ) + c infinitamente a menudo. ¡Entonces se podría decir que no podemos no generar algo que no sea la complejidad de Kolmogorov!c∈Z T(x)=K(x)+c
fuente
Creo que lo siguiente funciona. Usaré C ( x ) para la complejidad de KolmogorovC(x)
fuente