Si existe, se devuelve cierto. Prueba: supongamos que devuelve falso. Luego cae en un ciclo infinito y nunca termina. Esto es una contradicción.
Pero bastante más interesante es el programa Y que se puede derivar de X, y que detiene si y solo si sus parámetros no se detienen. Entonces Y (Y, Y) produce una contradicción: o se detiene (lo que significa que no se detiene), o no lo hace (en cuyo caso sí lo hace). Por lo tanto, X no existe. Los detalles se omiten, por ejemplo, hemos agitado un poco las manos en cuanto a si X e Y toman uno o dos parámetros.
Los problemas relacionados con la pregunta se debatieron en el siglo XIX: el décimo problema de David Hilbert (pedido en 1900) solicita un algoritmo para determinar si una ecuación diophantina dada tiene una solución. En retrospectiva, esto se puede expresar como un caso especial del problema de detención: encontrar un algoritmo para determinar si una búsqueda de fuerza bruta para una solución se detiene o no. Entonces X resolvería el décimo problema, pero la inexistencia de X dejó abierto el décimo problema. Finalmente se cerró en 1970, después de 20 años de trabajo de Martin Davis, Julia Robinson, Yuri Matiyasevich y otros. Hilbert declaró completamente el "Entscheidungsproblem" en 1928, que es la misma idea que el problema de detención, pero para probar si las afirmaciones en aritmética son verdaderas, en lugar de probar si los programas se detienen.
Creo que Alan Turing inventó la terminología necesaria para expresar el problema de detención como usted y probó el resultado (1936). Pero Alonzo Church había demostrado la existencia de problemas indecidibles en el cálculo lambda (también 1936), y los teoremas de incompletitud de Kurt Goedel (1931) hicieron tanto trabajo preliminar que usar sus técnicas para obtener esos resultados de computación fue probablemente un logro menor en ambos casos que formular los problemas habían sido (es decir, inventar el cálculo lambda y el modelo informático de Turing).
Relevancia para Russell Paradox (1901): sí, las pruebas tienen algo de la misma forma. En ambos casos, considera un objeto que representa un predicado evaluado en una clase que incluye el objeto mismo ("conjunto de todos los conjuntos, programa que actúa sobre los programas"). Asumes su existencia, permitiéndote construir un nuevo objeto modificando el predicado ("conjunto de todos los conjuntos que no son miembros de ellos mismos, programa que detiene si y solo si su entrada no se detiene"), produciendo una contradicción cuando intentas para evaluar el nuevo predicado "aplicado a sí mismo". Esto refuta la premisa ("existe un conjunto de todos los conjuntos", "existe un algoritmo para probar la detención").
Es posible que haya algo en la teoría de Topos (u otro análisis estructural de las matemáticas) que formalice la similitud, pero no sé lo que sería.
Sin embargo, hay una diferencia práctica significativa entre los resultados: la inexistencia de X simplemente prueba que el problema de detención no es decidible por un algoritmo, por lo que si eres David Hilbert tienes que volver a evaluar tus expectativas de lo que es posible en matemáticas Russell Paradox demostró que las teorías de los conjuntos en uso en ese momento eran inconsistentes, por lo que si eres Georg Cantor tienes que volver a evaluar cada prueba que hayas escrito. Esto provocó las primeras teorías axiomáticas formales formales, y re-declaraciones del trabajo de Cantor, Dedekind y otros teóricos del grupo, quienes habían estado trabajando con definiciones ingenuas de conjuntos que admitían la paradoja.
¿No es una pregunta real? La pregunta es, dado un cierto algoritmo X, cuál es el resultado de X (X, X). Es una pregunta muy real y relacionada con la programación. –
@Bruno Brant: lea el enlace en la respuesta aceptada para ver por qué no es realmente una pregunta real. Es como "Tenemos un motor. ¿Cómo hacer que su eficiencia sea 100% o más?". A primera vista, parece un problema de ingeniería interesante. – Roman
@Roman: La definición de "no es una pregunta real" es * "Es difícil decir lo que se pregunta aquí. Esta pregunta es ambigua, vaga, incompleta o retórica. no se puede responder razonablemente en su forma actual. "*. ¿Cuál de estas preguntas viola esta pregunta? – kennytm