정지 문제(Halting problem)의 간단한 증명

증명을 위해 정지 문제를 판별할 수 있는 함수 H가 존재한다고 하자. (귀류법)

함수 H는 판별할 함수 I를 인자로 받는다.

 

함수 H

 

이 때 함수 J를 아래와 같이 정의하면 모순이 발생한다.

 

함수 J

 

J의 인자로 J를 제공하면,

- H(J)가 참이라면 J는 언젠가 끝난다는 뜻이지만 J는 무한루프에 의해 끝나지 않는다. 

- H(J)가 거짓이라면 J는 끝나지 않는다는 뜻이지만 J는 return문에 의해 끝나게 된다.

 

따라서 이는 모순이다.