Muchos teoremas y "paradojas": la diagonalización de Cantor, la indecidibilidad de la incubación, la indecisión de la complejidad de Kolmogorov, la incompletitud de Gödel, la incompletitud de Chaitin, la paradoja de Russell, etc., tienen esencialmente la misma prueba por diagonalización (tenga en cuenta que esto es más específico de lo que pueden todo se demuestra mediante la diagonalización; más bien, se siente que todos estos teoremas realmente usan la misma diagonalización; para más detalles ver, por ejemplo , Yanofsky , o para una explicación mucho más breve y menos formalizada, mi respuesta a esta pregunta ).
En un comentario sobre la pregunta mencionada anteriormente, Sasho Nikolov señaló que la mayoría de ellos eran casos especiales del Teorema del Punto Fijo de Lawvere . Si se tratara de casos especiales, esta sería una buena manera de capturar la idea anterior: realmente habría un resultado con una prueba (la de Lawvere) de la cual todo lo anterior siguió como corolarios directos.
Ahora, para Gödel Incompletez e indecidibilidad del problema de detención y sus amigos, es bien sabido que siguen el Teorema del Punto Fijo de Lawvere (ver, por ejemplo, aquí , aquí o Yanofsky ). Pero no veo de inmediato cómo hacer eso por la indecidibilidad de la complejidad de Kolmogorov, a pesar de que la prueba subyacente es de alguna manera "la misma". Entonces:
¿Es la indecidibilidad de la complejidad de Kolmogorov un corolario rápido, que no requiere diagonalización adicional, del teorema del punto fijo de Lawvere?
fuente
Respuestas:
EDITAR: Agregar la advertencia de que el teorema de punto fijo de Roger puede no ser un caso especial de Lawvere.
Aquí hay una prueba que puede estar "cerca" ... Utiliza el teorema de punto fijo de Roger en lugar del teorema de Lawvere. (Consulte la sección de comentarios a continuación para obtener más información).
Deje ser la complejidad de Kolmogorov de la cadena x .K(x) x
lema . no es computableK .
Prueba .
Supongamos por contradicción que es computable.K
Defina como la longitud mínima de codificación de cualquier máquina de Turing M con L ( M ) = { x } .K′(x) M L(M)={x}
Existe una constante tal que | K ( x ) - K ′ ( x ) | ≤ c para todas las cadenas x .c |K(x)−K′(x)|≤c x
Función Definir tal que f ( ⟨ M ⟩ ) = ⟨ M ' ⟩ donde L ( M ' ) = { x } tal que x es la cadena mínimo tal que K ( x ) > | ⟨ M ⟩ | + c .f f(⟨M⟩)=⟨M′⟩ L(M′)={x} x K(x)>|⟨M⟩|+c
Como es computable, también lo es f .K f
Por el teorema del punto fijo de Roger , tiene un punto fijo, es decir, existe una máquina de Turing M 0 tal que L ( M 0 ) = L ( M ' 0 ) donde ⟨ M ' 0 ⟩ = f ( ⟨ M 0 ⟩ ) .f M0 L(M0)=L(M′0) ⟨M′0⟩=f(⟨M0⟩)
Según la definición de en la línea 4, tenemos L ( M 0 ) = { x } tal que K ( x ) > | ⟨ M 0 ⟩ | + c .f L(M0)={x} K(x)>|⟨M0⟩|+c
Las líneas 3 y 7 implican .K′(x)>|⟨M0⟩|
Pero por la definición de en la línea 2, K ′ ( x ) ≤ | ⟨ M 0 ⟩ | , contradiciendo la línea 8.K′ K′(x)≤|⟨M0⟩|
fuente