¿Existe un vínculo oculto entre la existencia de innumerables conjuntos y la indecidibilidad del problema de detención?

Dado que ambas pruebas hacen uso del argumento diagonal, me pregunto si existe un vínculo oscuro entre la existencia de incontables conjuntos infinitos y la indecidibilidad del problema de detención. ¿El problema de detención sería decidible si todos los conjuntos fueran contables?

halting-problem Lenar Hoyt
fuente

Sí, el argumento diagonal!

Mahdi Cheraghchi

@MCH Pensé que quizás haya una caracterización diferente además del argumento diagonal que conecta a ambos. Esta pregunta es quizás demasiado borrosa para SE.

Lenar Hoyt

Esto puede ser un enlace parcial: claramente, el conjunto de todos los idiomas en un alfabeto dado es incontable. Sin embargo, el conjunto de todas las máquinas de Turing es contable. Esto implica directamente la existencia de problemas indecidibles. Sin embargo, este razonamiento no implica nada sobre el problema de detención.

042

Ciertamente, hay modelos teóricos de conjuntos de ZFC donde todos los conjuntos son contables (aunque no dentro del modelo), pero el problema de detención siempre es indecidible. Vea esta pregunta de MathOverflow .

Peter Shor

Por favor, por favor diga indecidibilidad de ahora en adelante.

Vijay D

Respuestas:

No es un enlace oculto, sino uno que se ha hecho explícito utilizando el lenguaje de la teoría de categorías y también una pregunta muy natural para hacer y estudiar. Hay bastante material sobre el tema.

Pregunta de la teoría de CS que pregunta lo mismo
Publicación de blog de Andrej Bauer sobre teoremas de punto fijo y teorema de Cantor.
Un enfoque universal para las paradojas autorreferenciales, la incompletitud y los puntos fijos , Noson Yanofsky, 2003. A continuación, se presenta una introducción suave al artículo de Lawvere.
Argumentos diagonales y categorías cerradas cartesianas , F. William Lawvere, 2006 republicación de un artículo de 1969 que hace precisas estas conexiones.
Incompletitud en un entorno general , John Bell, 2007
De Lawvere a Brandenburger-Keisler: formas interactivas de diagonalización y autorreferencia , Samson Abramsky y Jonathan Zvesper, 2010. Extensión de los argumentos de Lawvere a resultados de imposibilidad teórica del juego.

Vijay D
fuente