컴퓨터과학이 여는 세계_3.4 멈춤문제를 이용한 튜링의 불완전성 증명_이광근
멈춤문제: 어떤 튜링기계가 멈출지 멈추지 않을지를 정확히 판단해내는 문제
멈춤문제를 해결하는 튜링기계는 만들 수 없다!
이전에 한 튜링기계가 다른 튜링기계를 따라하는 튜링기계를 만들 수 있다고 하였다. 그런데 이번에는, 어떤 튜링기계를 입력받으면 그것을 쭉 살펴보고 유한시간이 지난 후 '유한시간만에 끝나겠다.' 혹은 '영원히 끝나지 않겠다.' 라는 것을 스스로 판별하는 튜링기계를 고안하려고 한다.
한편 모든 수리명제를 자동판결하는 튜링기계를 만들 수 있다면, 이 멈춤문제를 해결하는 튜링기계를 당연히 만들 수 있다. 그런데, 이 멈춤문제를 해결하는 튜링기계를 만들 수 없다. 따라서 모든 수리명제를 자동판결하는 튜링기계를 만들 수 없다.
다시 말하자면
모든 수리명제를 자동판결하는 튜링기계를 만들 수 있다. --A
멈춤 문제를 해결하는 튜링기계를 만들 수 있다. --B
라고 했을때,
A이면 B이다. (참)
~B이면 ~A이다. (대우 - 참)
그런데 B가 거짓이므로 A도 거짓이 된다. ('~A'는 'A가 아니면' 이라는 뜻이다)
그렇다면 멈춤 문제를 해결하는 튜링기계(이하 H.튜링기계)가 존재하지 않음을 어떻게 증명할까.
먼저, H.튜링기계가 있다고 하자. H.튜링기계는 임의의 튜링기계하나랑 그 임의의 튜링기계에 입력할 입력값들을 입력 받아 그 기계가 유한시간만에 멈추면 1 절대 멈추지 않으면 0을 반환한다고 하자.
(M은 튜링기계를, I는 입력값을 뜻한다)
이전 포스팅에 튜링기계는 자연수 갯수 만큼있고, 입력값 또한 자연수 갯수만큼 있다는 것이 성립함을 증명했다. 따라서, Mn과 In은 자연수갯수 만큼 존재한다.
자, 이제 새로운 튜링기계 D(n)을 정의하자.
D(n)은 어떤 튜링기계 Mn과 입력값 In가 있을 때, H.튜링기계에 Mn과 In을 입력하고 만약 Mn이 유한시간 만에 끝난다면, Mn에 In을 입력했을 때의 결과값에 + 1을 한것을 반환한다. 반면, H.튜링기계에서 Mn이 In을 입력받았을 때 유한시간만에 끝나지 않아 영원히 반복한다면, 그냥 1을 반환한다. H.튜링기계에서 유한시간 만에 끝났을 때를 1 안끝났을때를 0 이라 했기에 다음과 같이 쓸 수 있다.
그런데, 이 튜링기계는 기존의 자연수 갯수만큼 있던 튜링기계랑 서로 다르다. 따라서 자연수 갯수 만큼 존재한다는 튜링기계에 모순이 생겨버렸다. 따라서, 멈춤문제를 해결하는 튜링기계는 존재하지 않는다.