¿Existe un conjunto infinito de cadenas cuyas complejidades de Kolmogorov sean computables?
Respuesta
¿Demasiados anuncios?
Creo que estás preguntando lo siguiente: ¿existe un conjunto r.e. infinito de pares $(\sigma,n)$ donde $\sigma \in 2^{<\omega}$ es una cadena de complejidad Kolmogorov $n$ . La respuesta es no.
Para contradecirnos, supongamos que dicha lista es r.e. - entonces hay cadenas arbitrariamente largas en ella, y por tanto cadenas de complejidad de Kolmogorov arbitrariamente alta. Definamos una función $P$ que toma la entrada $\tau \in 2^{<\omega}$ y hace lo siguiente. En primer lugar, enumera efectivamente esa lista hasta que encuentra un par $(\sigma, n)$ donde $n > |\tau|$ . Luego imprime $\sigma$ .
Las suposiciones que hemos hecho garantizan que $P$ es una función totalmente computable. Por lo tanto, aplicando el teorema de recursión de Kleene a $P$ da un programa $e_0$ que, cuando se ejecuta sin entrada, calcula $P(e_0)$ . Así, la salida del programa $e_0$ ejecutada sin entrada, es una cadena de complejidad Kolmogorov mayor que $|e_0|$ lo cual es imposible.
