Se sabe que con un conjunto contable de algoritmos (caracterizado por un número de Gödel), no podemos calcular (construir un algoritmo binario que verifique la pertenencia) todos los subconjuntos de N.
Una prueba podría resumirse como: si pudiéramos, entonces el conjunto de todos los subconjuntos de N sería contable (podríamos asociar a cada subconjunto el número de Gödel del algoritmo que lo computa). Como esto es falso, prueba el resultado.
Esta es una prueba que me gusta, ya que muestra que el problema es equivalente a que los subconjuntos de N no sean contables.
Ahora me gustaría demostrar que el problema de detención no se puede resolver utilizando solo este mismo resultado (incontabilidad de N subconjuntos), porque supongo que son un problema muy cercano. ¿Es posible demostrarlo de esta manera?
Respuestas:
El teorema de detención, el teorema de Cantor (el no isomorfismo de un conjunto y su conjunto de potencias) y el teorema de incompletitud de Goedel son todas instancias del teorema del punto fijo de Lawvere, que dice que para cualquier categoría cartesiana cerrada, si hay un mapa epimórfico entonces cada f : B → B tiene un punto fijo.e : A → ( A ⇒ B ) F: B → B
Para una buena introducción a estas ideas, vea esta publicación de blog de Andrej Bauer .
fuente