¿Es la complejidad de Kolmogorov una función surjective?

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 modo que U (p) = x.

¿Hay una N tal que para todo n> N haya una x con K (x) = n?

Observación. Si definimos máquinas Turing universales de una manera diferente, la respuesta puede ser negativa. Por ejemplo, considere una U que en la entrada (T, x) simula T en x si la longitud de (T, x) es divisible por 100, y de lo contrario no hace nada. Se puede modificar este ejemplo de varias maneras para obtener contraejemplos para diferentes definiciones de máquinas Turing universales.

cc.complexity-theory universal-computation kolmogorov-complexity universal-turing-machines domotorp
fuente

Lejos de lo que estás pidiendo, pero creo que no es difícil de probar que la imagen de tiene una densidad lineal positiva independientemente de . Esto implica, por ejemplo, que es infinitamente compuesta.

K

$K$

U

$U$

K (x)

$K(x)$

Dan Brumleve

Respuestas:

Solo un comentario extendido sin conocimientos profundos: tal vez pueda engañar a la codificación de una máquina de Turing y construir una codificación artificial que conduzca a una complejidad de Kolmogorov surjective:

representa la máquina de Turing que emite (1 estado TM); $0$ $0$
representa la máquina de Turing que emite (el número representado por la cadena binaria más uno); es simplemente una versión "comprimida" implícita de una TM decidible que genera ; $0p$ $p+1$ $p$ $p+1$
representa la -máquina de Turing en una enumeración estándar (la enumeración puede omitir los TM ya incluidos con y ). $1p$ $p+1$ $0$ $0p$

La TM universal correspondiente en la entrada verifica cuál es el valor de , si es , simplemente genera , de lo contrario simula TM ( cuando es la cadena vacía); tenga en cuenta que incrusta las entradas. $bx$ $b$ $0$ $x+1$ $M_{x+1}$ $M_0$ $x$ $M_{x+1}$

Para todas las cadenas , ; y para todos los hay cadenas de longitud pero solo hay programas de longitud que se pueden representar utilizando la codificación ; y solo programas de longitud que se pueden representar usando el $x$ $1 \leq K(x) \leq |x|+1$ $n \geq 1$ $2^{n}$ $n$ $2^{n-1}-1$ $< n$ $1p$ $2^{n}-1$ $n$ $1p$ codificación entonces al menos una cadena de longitud no se puede representar con un programa de longitud ; pero seguramente se puede representar con el programa de longitud (no nos preocupamos si también hay un programa de la misma longitud que lo genera). $x'$ $n$ $1p$ $\leq n$ $0x'$ $n+1$ $1p$ $n+1$

Podemos concluir que para todo , existe una cadena tal que (por lo que este K particular es sobreyectivo). $n > 1$ $x', |x'|=n$ $K(x') = n+1$

Marzio De Biasi
fuente