Halting Problem (정지 문제)

오늘을 Halting Problem 이라는 유명한 판정 문제를 소개해 보겠습니다.

Alan Turing의 증명과 내 나름의 이해한 것을 바탕으로 풀이를 써보았습니다.

 

 

The Halting Problem

- 프로그램 M 과 입력 X 가 있을 때 M에 입력 X를 주고 수행시키면 M은 종료할 것인가?

이 프로그램 M이 계산을 끝나고 멈출지, 아니면 영원히 멈추지 않을지 판정하라.

 

Halting Problem 이라는 유명한 문제인데 이 문제를 처음 봤을 때는 이게 뭐지...? 싶었다.

프로그램 M이 멈추냐, 안 멈추냐 뭐 이런 뜻 같은데.... 상황에 따라 멈출 수도 있고 안 멈출수도 있지 않나? 라고 생각했다.

"상황에 따라서" 말이다.

당연한 얘기일 것이다. 프로그램을 어떻게 짜느냐에 따라 멈출 수도 있고, 안 멈출수도 있겠지.

 

그러나"상황에 따라서" 라는 말은 경우의 수가 무한히 많다고 한다.

 

멈추지 않는 프로그램의 예를 들자면,

while(1){} , while(1>0){} ..... 이렇게도 무한히 만들 수 있고

main 함수 안에 int x = 3;  인데 x=3 이면 무한 루프를 돌게 시키는 등.... 무수하게 많다.

 

이를 Alan Turing 이라는 분이 이 문제는 판정 불가한 문제라는 것을 증명했다고 하는데, 그의 증명을 소개하도록 하겠다.

 

 

Proof By Alan Turing

여기서 프로그램 M , 입력 X에서 이 M과 X는 전부 문자열이라고 보는게 편하다.

프로그램 소스코드는 결국 다 문자열이기 떄문에, 그냥 문자열이라 가정하자.

 

M에 입력 X를 준다는 건 M(X) 라는 뜻이고, 프로그램 M에 입력 X를 주고 실행한 상태를 의미한다. 

M(X) : 프로그램 M에 입력 X를 주고 실행시킨 상태.

M(X)는 종료(exit) or 종료하지 않음(loop)

 

여기서 항상 종료하는 프로그램 D가 있다고 가정하자.

가정 : 어떤 경우에도 항상 종료하는 프로그램 D가 존재한다.

 

그렇다면 당연히 D(M,X)는 종료한다. 

 

D(M,X):

• M(X) : exit ㅡ> D : yes 출력 (D는 멈춤)
• M(X) : loop ㅡ> D: no 출력 (D는 멈춤)

D'(M,X) :

• M(X) : exit ㅡ> 멈추지 않음
• M(X): loop ㅡ> 멈춘다

D'은 D(M,X)를 돌려 D가 yes를 출력하면 멈추지 않게, no를 출력하면 멈추도록 짜면 된다.

 

이런 프로그램인 D'도 얼마든지 존재할 것이다. M(X)가 종료하면 loop 를 돌려서 D'을 멈추지 않게, M(X)가 종료되지 않으먄 return; 해서 D'을 멈춰버리면 된다.

 

S(M) :

• M(M)이 멈추는 경우 S(M)은 멈추지 않고 
• M(M)이 멈추지 않는 경우 S(M)은 멈춘다.

S가 M을 입력으로 받으면, D(M,M)을 돌리기만 하면 된다. D(M,X)에서 X자리에 D만 넣으면 되니까.

 

M(M)이 어떻게 가능하냐고?...

사실 자신을 자신의 인자로 주는 프로그램은 많지 않다.(사실 없다고 봐야될듯...?)

그렇지만 처음에 M 그리고 모든 프로그램은 문자열로 보자고 했었다. 문자열은 모든 입력으로 가능하므로 M의 입력으로도 줄 수 있다.

 

위의 S 를 잘 보고... 다음 문장을 보자.

 

S(S) :

• S(S)가 멈추는 경우 S(S)는 멈추지 않는다.
• S(S)가 멈추지 않으면 S(S)는 멈춘다.

 

??????????????

 

확실히 이상한 문장이다...ㅋㅋ 말이 되지 않는다.

그럼 어디가 잘못된거지? 거슬러 올라가보자.

거슬러 올라가다 보면 시작 자체가 잘못 되었다는 것을 알 수 있는데.

 

D는 무조건 종료하는 프로그램이다. 이 말 자체가 잘못되었다. 

무조건 종료하는 프로그램 D는 없다!

 

따라서 귀류법으로 AlanTuring 은 이 정지 문제가 해결할 수 없는 문제라는 것을 증명하였다.

 

귀류법이란

어떤 명제를 참이라고 가정하고 함의하는 내용을 계속 따라가다 보면 모순이 생기는 결론에 도달하게 되는데, 이렇게 함으로써 처음 명제가 잘못되었다는 것을 밝히는 증명법 중 하나이다.

 

case by case 로는 따질 수 있겠지만, 앞서 얘기했든 모~~든 경우를 따지는 것은 사실 불가능하다.