¿La complejidad de Kolmogorov es casi sobreyectiva?

8

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 queK
cn
xn<K(x)<n+c?

A diferencia de la pregunta que me inspiró , la respuesta de esta pregunta es sólida frente a la elección deK, ya que por definición es un "lenguaje de descripción esencialmente óptimo" si y solo si es una función parcial computable de{L0
a sí mismo de modo que para todas las funciones parciales computables L{0,1}
de{L1 para sí mismo, existe un enterocy una función computable (total){0,1}
cf:{0,1}{0,1}tal que
para todas las cadenas ,xlength(f(x))<length(x)+c y L0(f(x))=L1(x).

Comunidad
fuente
1
¿Puede agregar más detalles sobre "lenguajes de descripción esencialmente óptimos"? Uno puede definir el lenguaje simple (¿óptimo?) "1" imprime 1 y "0" imprime 0 y obtiene una inducida que satisface su condición, pero sostengo que esto no es lo que quiere :-)K
Marzio De Biasi
Yo solo lo hice.
Heurísticamente, uno pensaría que sí, ya que hay tantas cadenas cuyo KC está dentro de una constante de su longitud ...
usul

Respuestas:

6

L0{0,1}fC|f(x)||x|+CL0(f(x))=x

xnK(x)nK(x)n+C

Yuval Filmus
fuente