Turing es una prueba de la undecidability de la detención problema es lo suficientemente fácil como para ser explicado a la mayoría de los estudiantes de matemáticas que están familiarizados con la forma en que los programas de ordenador de trabajo, pero es de gran importancia en su campo.
Puede ser utilizado para probar Gödel del teorema de la incompletitud (si asumimos $\omega$-consistencia de PA): dado un programa de $P$ en alguna máquina de Turing, la declaración de que $P$ detiene puede ser codificado como una sentencia de $s_P$ de la Aritmética de Peano. Si el teorema de completitud eran falsas, entonces no sería una prueba de cualquiera de las $s_P$ o $\neg s_P$.
Pero esto ahora nos da un algoritmo para la detención problema, en contradicción de la prueba de Turing: dado un programa de $P$, iterar a través de todas las posibles pruebas en la Aritmética de Peano hasta llegar a una prueba de $s_P$ o una prueba de $\neg s_P$. Por lo anterior, este algoritmo está garantizado para terminar.
En un sentido, sin embargo, esta es la misma respuesta que la de la diagonal argumento.