튜링의 재귀적 정지 문제 증명

참고 자료:
https://namu.wiki/w/%EC%A0%95%EC%A7%80%20%EB%AC%B8%EC%A0%9C

원본 튜링의 정지 문제 증명은 튜링 머신과 대각선 논법을 통해 증명하나,
러프하게 재귀와 소스 코드 만으로도 할 수 있다.

<귀류법과 재귀>

어떤 프로그램과 입력 값을 인자로 받아 입력에 대한 프로그램의 동작이 무한한지, 멈추는지
판별이 가능한 프로그램 D가 있다고 하자. (귀류)
$$D(M, X) = {YES, NO} (M=Program, X=input)$$
멈추면(끝나는게 가능하면) YES, 무한히 돌아가면 NO
그러면 D의 출력과 반대로 출력을 하는 프로그램도 가능할 것이다.
$$D'(M,X) = {NO, YES}$$
D가 YES일 때, D'은 NO, D가 NO일 때 D'은 YES인 프로그램 D'은 당연히 가능하다.
그리고 X가 프로그램 M 그 자체일 때(입력이 M의 소스 코드일 때)
$$D(M, M) = M(M)$$
이라고 하자.
프로그램 S(M)는 어떤 프로그램 M의 M(M) 결과 값에 반대 값을 내놓는다. (=D와 D' 관계)
그렇다면 다음의 경우에는 어떻게 되는가?
$$S(S)$$
S가 YES일 때는 NO여야 하고, S가 NO일 때는 YES여야 한다. 동시에 2가지 상태를 가지는 모순이 생긴다. 결국 S 자체가 불가능하다는 결론에 이르게 되고, 이는 곧 맨 처음에 가정한 프로그램 D가 존재할 수 없다는 것이다. 즉, 정지 판별이 가능한 D는 없다는 사실이 된다.