Cálculo de la complejidad de Kolmogorov de Turing-Idioma incompleto

Question

Estoy tratando de determinar si la complejidad de Kolmogorov es computable para un idioma específico. Estoy seguro de que este lenguaje dado no está tratando. El idioma se define de la siguiente manera:

$ a; b \ texto {Ejecuta las instrucciones A y B one tras la otra.} $
$! x_i! \ Text {- Configura variable} x_i \ texto {al valor} 2. $
$ \ {x_i \} \ texto {- Douza el valor de la variable} x_i $
$ [x_i] \ texto {- mitades El valor de la variable} x_i \ texto {y lo redondea.} $
$ "w" \ texto {- imprime la cadena} w \ in \ {a, b, ..., z, a, b ..., z \} $
$ \ lambda (x_i, a) \ texto {- ejecuta instrucciones} A \ texto {exactamente} x_i \ texto {veces, independientemente de los cambios posteriores a} x_i $ < / p>

Específicamente, necesito saber si la complejidad de Kolmogorov en relación con este idioma es generalmente computable. El programa que calcula esta complejidad se puede escribir en un lenguaje completo de Turing.

Entiendo que para cualquier lenguaje completo de Turing, la complejidad de Kolmogorov no es computable. Este idioma aquí carece de la capacidad de crear un bucle Infinte, sin embargo, y como tal es menos que Turing-Completa. Sin embargo, no estoy sintiendo ninguna intuición derivada de esta observación. Supongo que, este lenguaje será más débil, la complejidad de Kolmogorov puede ser computable ahora. Sin embargo, no puedo encontrar una prueba para esto. Dar un algoritmo que cumple esta tarea parece demasiado complicada. El uso de este idioma parece un caso especial de la computabilidad más general de la complejidad de Kolmogorov y, como tal, no puedo derivar de los atributos del caso general si el caso general no es computable. Esto todavía puede ser.

No estoy encontrando ningún lugar para enfrentar este problema y daría la bienvenida a cualquier consejo y punteros hacia una solución. ¿Podemos deducir algo más de este idioma que lo que he mencionado hasta ahora? ¿Es una potencia más baja en relación con los idiomas completos de Turing, nos ayudan con esta situación?

Answer 1

Lo importante que debe notar es que sus programas siempre se detienen. Esto facilita la computación de la complejidad de Kolmogorov una tarea fácil, ya que se le dio una cadena $ w $ , puede repasar todos los programas posibles de longitud $ \ le | w | +2 $ para encontrar el programa más corto cuya salida es $ w $ . El encuadernado superior $ | w | +2 $ sigue del hecho de que para cualquier cadena $ w $ , "W" es un programa cuya salida es $ w $ .

De hecho, probablemente podría calcular la complejidad de una cadena en el tiempo polinomial, ya que la compresión solo es posible en el caso de repeticiones (no puede aprovechar una estructura más general). Algo a lo largo de las siguientes líneas debe trabajar $ kc (w_1 ... w_n)=min \ limits_i \ big (kc \ izquierda (w_ {i + 1} ... w_n | w_i \ Derecha) + KC (W_1 ... W_I) \ BIG) $ , donde $ kc \ izquierda (W | w '\ derecha) $ es Just $ kc (w) $ si $ w '$ no es un prefijo de $ W $ , y $ kc (w '') + o (\ log j) $ de lo contrario donde $ w= w '^ jw' $ y $ j $ es el número máximo que satisface esto. El punto es que solo necesita calcular la complejidad de las subcadenas de $ w $ , de los cuales hay $ O (| w | ^ 2) $ .