Al mejor de mi conocimiento, de los dos grandes avances en cuanto a negativos resultados en la computación/teoría de la recursividad llegó en 1936 por la Iglesia y de Turing. Ambos demostrar que algunas variantes de la detención problema era indecidible.
Sin embargo, una prueba simple de la declaración "No es un problema indecidible" ya existía en ese momento, es decir, el hecho de que simplemente hay demasiados problemas y muy pocos algoritmos.
Suponiendo que el algoritmo tiene un número finito de descripción, y que se lleva naturales números como entrada, estamos tratando de hacer un bijection entre los números naturales $\mathbb{N}$ y su powerset $2^{\mathbb{N}}$.
La adopción de Cantor diagonal de argumento para Máquinas, podemos observar que si $\mathcal{M} = \{M_i \mid i \in \mathbb{N}\}$ es el conjunto de máquinas, y para cada máquina $M \in \mathcal{M}$, $M(n)$ es sí (se detiene) o no (no no halt), para $n \in \mathbb{N}$.
Entonces podemos construir el conjunto $$U = \{i \in \mathbb{N} \mid M_i(i) \text{ is no} \}$$ como Cantor, y elija la $i$ s.t. el dominio de $M_i$$U$, y pedir si $i \in U$, en ambos casos, llegar a una contradicción.
Pregunta: ¿por Qué no esta descubierto entre 1875/90 y 1935? (¿O era?)
