Hay muchas formas de definir la complejidad de Kolmogorov y , por lo general, todas estas definiciones son equivalentes hasta una constante aditiva. Es decir, si y K 2 son funciones de complejidad kolmogorov (definidas a través de diferentes lenguajes o modelos), entonces existe una constante c tal que para cada cadena x , | K 1 ( x ) - K 2 ( x ) | < c . Creo que esto se debe a que para cada función de complejidad de Kolmogorov K y para cada x contiene , para alguna constante c .
Me interesan las siguientes definiciones para , basadas en máquinas de Turing
- número de estados : defina como el número mínimo q de modo que una TM con q estados genere x en la cadena vacía.
- x
¿Son y equivalentes? ¿Cuál es la relación entre ellos y cuál comprende mejor el concepto de complejidad de Kolmogorov, si no son equivalentes?K 2
Lo que me molesta especialmente es la tasa de aumento de con , que parece no ser (o al menos lineal con constante modo que , en lugar de ). Considere la TM más simple que genera , la que solo codifica como parte de sus estados y funciones de transición. Es inmediato ver que . Sin embargo, la codificación de la misma máquina es mucho mayor, y el límite trivial que obtengo es. x C > 1 K 2 < C | x | El | x | + c x x K 1 ( x ) ≤ | x | + 1 K 2 ( x ) ≤ | x | log | x |
Respuestas:
Me disculpo de antemano por dar muchos detalles, pero estoy a punto de contradecir a las personas.
Acerca deK(x)≤K′(x)+c
El hecho de que generalmente proviene de un intérprete del lenguaje de descripción n. ° 2 en el lenguaje de descripción n. ° 1 y no de una traducción de los programas del n. ° 2 a los programas del n. ° 1.K1(x)≤K2(x)+c
Por ejemplo, y obtienes esta desigualdad de la siguiente manera:KC(x)≤KPython(x)+cpy2c
Entonces su constante será algo así como donde es el número de bits para este código y bits es el tamaño que el intérprete oficial de Python escribió en C. Por supuesto, solo necesita interpretar lo que es posible en su lenguaje de descripción para Python para que pueda hacerlo mejor que 69 MB :-) 528 + 490240688 528 490240688cpy2c 528+490240688 528 490240688
Lo importante es que puede escribir su programa Python linealmente en su código C. Por ejemplo, un lenguaje en el que necesita poner "BANANA" entre cada carácter no es un programa de descripción muy bueno y la propiedad es falsa. (Pero si el lenguaje de descripción lo autoriza a escribir datos en un archivo separado o en un bloque, este problema desaparecerá)
¿Por qué su es defectuoso?K1(x)=q
El problema con su definición de es que puede necesitar más de bits para describir una máquina de Turing con estados porque necesita codificar transiciones. q qK1 q q
Entonces, no y probablemente no sean equivalentes, pero eso es principalmente de . Creo que podemos demostrar que para todo hay una tal que . Por supuesto, cualquier es suficiente para refutar el hecho de que no es una función válida, ya que significaría que podemos codificar más todas las cadenas posibles de longitud en bits.K1 K2 K1 a>0 ca K1(x)≤a|x|+ca a<1 K1 2n n an+ca
Pero el tamaño es increíblemente estrecho cuando se construyen máquinas Turing. La idea es que en un bloque de estados hay formas de encontrar transiciones para cada estado y eso es mejor que las formas habituales de para llenar bits. Luego puede almacenar en cada bloque bits de información. (no porque tienes que entrar y salir del bloque de una forma u otra)b b2b 2b b log2b 2log2b
Entonces sí ... Con bloques de tamaño probablemente probar . Pero ya escribí demasiado sobre por qué el número de estados no es una función de complejidad de Kolmogorov válida. Si quieres que explique, lo haré.21/a K1(x)≤a|x|+ca
Ahora sobreK2
El lenguaje descriptivo ingenuo corresponde aproximadamente a (es decir, para cada estado siguiente y detalles sobre escritura y terminación).K2(x)=q⋅2⋅(log2q+2) log2q
Como parece, estoy convencido de que una forma mejor / engañosa sería autorizar la codificación de "datos" en la máquina Turing, tal vez agregando una etiqueta binaria en el lenguaje de descripción que diga si un estado es un estado de datos ( que solo escribe un poco y pasa al siguiente estado) o si hace algo más. De esa manera, podría almacenar un poco de su en un poco de su lenguaje descriptivo.x
Sin embargo, si mantiene el mismo , podría usar la misma técnica que utilicé en la parte anterior para guardar algunos bits, pero parece que estoy atascado en (para cualquiera ) .. quizás menor que, incluso, pero obtener parece difícil. (Y espero que sea , ni siquiera .)K2 K2(x)≤a|x|log|x|+c a>0 log|x| O(|x|) |x| O(|x|)
fuente