La prueba de la complejidad de Kolmogorov es indiscutible utilizando reducciones

Estoy buscando una prueba de que la complejidad de Kolmogorov es indiscutible utilizando una reducción de otro problema incontestable. La prueba común es una formalización de la paradoja de Berry en lugar de una reducción, pero debe haber una prueba reduciendo algo como el Problema de detención o el Problema de correspondencia de Post.

Puede encontrar dos pruebas diferentes en:

Gregory J. Chaitin, Asat Arslanov, Cristian Calude: La complejidad del tamaño del programa calcula el problema de detención. Boletín de la EATCS 57 (1995)

En Li, Ming, Vitányi, Paul MB; Una introducción a la complejidad de Kolmogorov y sus aplicaciones se presenta como un ejercicio (con una pista sobre cómo resolverla que W. Gasarch acredita a P. Gács en una comunicación personal el 13 de febrero de 1992).

** Decidí publicar una versión extendida en mi blog .

Esta fue una pregunta divertida para pensar. Como se describe en la otra respuesta y en los comentarios a continuación, hay una reducción de Turing del problema de Detención a la computación de la complejidad de Kolmogorov, pero en particular no existe tal reducción de muchos, al menos para una definición de 'computación de la complejidad de Kolmogorov'.

Definamos formalmente de qué estamos hablando. Deje que denote el lenguaje estándar de TM que se detiene cuando se le da una descripción de sí mismos como entrada. Deje K O denotan { ⟨ x , k ⟩ | x  tiene la complejidad de Kolmogorov exactamente  k } .$HALT$$KO$$\{ \langle x,k \rangle \mid x \text{ has Kolmogorov complexity exactly } k \}$

Suponga que por alguna reducción de muchos. Sea f : { 0 , 1 } ∗ → { 0 , 1 } ∗ denota la función que calcula esta reducción. Considere la imagen de H A L T debajo de f , que denotaré f ( H A L T ) .$HALT \le KO$$f: \{0,1\}^* \rightarrow \{0,1\}^*$$HALT$$f$$f(HALT)$

Nota consiste en cadenas de la forma ⟨ x , k ⟩ donde x tiene complejidad Kolmogorov exactamente k . Afirmo que las k que ocurren en f ( H A L T ) son ilimitadas, ya que solo hay un número finito de cadenas con la complejidad de Kolmogorov exactamente k , yf ( H A L T ) es infinito.$f(HALT)$$\langle x,k\rangle$$x$$k$$k$$f(HALT)$$k$$f(HALT)$

Como es recursivamente enumerable (también conocido como Turing-reconocible en algunos libros), se deduce que f ( H A L T ) es recursivamente enumerable. Combinado con el hecho de que los k 's son sin límites, podemos enumerar f ( H A L T ) hasta que encontremos alguna ⟨ x , k ⟩ con k tan grande como queremos; es decir, existe un TM M que en la entrada k da salida a algún elemento ⟨ x , k $HALT$$f(HALT)$$k$$f(HALT)$$\langle x,k\rangle$$k$$M$$k$ .$\langle x,k \rangle \in f(HALT)$

Escriba una nueva TM que haga lo siguiente: primero, calcule | M ′ | usando el teorema de recursión de Kleene. Consulta M con entrada | M ′ | + 1 para obtener ⟨ x , | M ′ | + 1 ⟩ ∈ f ( H A L T ) . Salida x .$M'$$|M'|$$M$$|M'|+1$$\langle x, |M'|+1\rangle \in f(HALT)$$x$

Claramente, la salida de M ' es una cadena con complejidad de Kolmogorov como máximo | M ′ | pero ⟨ x , | M ′ | + 1 ⟩ ∈ f ( H A L T ) que es una contradicción.$x$$M'$$|M'|$$\langle x, |M'|+1\rangle \in f(HALT)$

Creo que también puede sustituir en el problema "Complejidad de Kolmogorov exactamente " con "Complejidad de Kolmogorov al menos k " con cambios menores.$k$$k$