힐베르트가 수학에서 기계적으로 모든 참인 명제를 찾아낼 수 있는 무모순적인 공리계를 찾으려고 했었고(힐베르트 프로그램), 괴델이 그것을 반증했다(불완전성의 정리). 괴델 이후 튜링은 그 '기계적인 방식'을 튜링기계를 통해서 정의하고 모든 참인 명제를 만드는 튜링기계는 없다는 것을 증명해낸다.
멈춤 문제는 그 증명의 열쇠 역할을 한다. 어떤 기계가 멈출지 멈추지 않을지 판단하는 기계가 존재하는가? 모든 참인 명제를 차례로 만들어낼 수 있는 튜링기계 \(A\)가 있다면, 이 기계는 충분히 강력해서 멈출 것인지 판별할 기계 \(M\)을 입력으로 받아 언젠가는 '\(M\)은 멈춘다' 또는 '\(M\)은 멈추지 않는다'라는 명제를 도출해낸다. 즉, \(A\)가 있으면 멈춤 판별을 하는 기계 \(H\)도 존재한다.
멈춤 문제의 답은 False로, 증명은 튜링 기계의 개수를 통해 모순성을 도출해낸다. 임의의 튜링기계는 테이프에 일렬로 나타낼 수 있고 테이프에 사용되는 문자는 유한하기 때문에 튜링기계의 개수는 자연수의 개수를 넘지 못한다. 그래서 모든 튜링기계에 자연수 번호를 붙여볼 수 있고(\(M1, M2 M3, \cdots \)), 입력도 튜링기계가 만들어지는 속도만큼 빠르게 만들어낼 수 있다(\(I1, I2, I3, \cdots \)). \(H\)가 존재한다고 가정하면 기계와 입력이 주어졌을 때 멈출 것인지, 멈추지 않을 것인지 계산한 결과가 언제나 결정된다.
멈춤 기계에 튜링기계 \(M\)과 입력 \(I\)를 넣어서 도출한 결과를 내는 함수 \(Halt(M,I)\)를 정의했을 때, \(Halt(M1,I1), Halt(M2,I2), Halt(M3,I3) , \cdots \)의 결과들을 얻을 수 있다. 이 때 각 결과의 부정형만 출력하는 튜링기계를 생각해보면, 이 튜링기계는 모든 튜링기계와 다른 기계가 되므로 모순이다.
가정을 다시 살펴보면 '멈춤 기계는 존재한다'와 '모든 튜링기계를 순서대로 나열할 수 있다'가 있는데, 후자는 참이므로 전자가 거짓이다.