정지 문제(Halting Problem) - 최고의 컴퓨터도 만들 수 없는 프로그램이 존재한다

1. 정지 문제(Halting problem)

 

프로그램을 만드는 사람이라면 누구나 이런 생각을 한다.

 

"내가 만든 프로그램을 실행하면 정상적으로 종료될지, 무한 루프를 돌지, 실행하지 않고 아는 방법이 있을까?"

 

그러면 내가 짠 프로그램 D가 정상적으로 종료되는지, 무한 루프를 도는지 검사해주는 또 다른 프로그램 H를 만들면 되는거 아닌가?

 

그러한 프로그램 H가 존재한다고 가정해보자.

 

H는 분석할 프로그램 D와 프로그램 D의 입력 I를 입력으로 받고, D가 정상적으로 종료하면 True

 

무한루프를 돌면 False를 유한 시간 내에 return하는 함수이다.

 

어떤 프로그램 P는 프로그램 H에 다음과 같이 물어본다.

"프로그램 D에 입력으로 프로그램 D를 주면 어떻게 되냐?"

 

만약 H가 정상적으로 종료된다라고 말하면, 무한루프를 발생시키고, H가 무한루프를 돌면 정상적으로 종료된다.

 

def P(D):
    # H에게 "프로그램 D에 소스코드 D를 입력으로 넣으면 어떻게 돼?"라고 물어봄
    if H(D, D) == True:
        # H가 "그거 정상적으로 정지해!"라고 하면
        while True: pass  # 일부러 영원히 끝내지 않고 무한 루프를 돈다.
    else:
        # H가 "그거 무한 루프에 빠져!"라고 하면
        return True       # 즉시 정상 종료(정지)한다.

 

 

프로그램 D의 입력으로 프로그램 D를 준다는 뜻은 무슨 뜻인가?

 

오류를 검사해주는 컴파일러라는 프로그램은 입력으로 어떤 프로그램을 검사하여,

 

프로그램이 오류가 있는지 검사해주는데 이와 마찬가지다.

 

컴파일러는 자기 자신의 소스 코드를 컴파일하는 self hosting이 존재하고

 

바이러스 검사 프로그램은 자기 자신을 검사하는 경우도 가능하다.

 

 

---------------------------------------------------------------------------------------------------------------------

 

 

이제 이 함수 P에 입력으로 P를 준다면?

 

 

P(P)

 

 

내부에서 H(P,P)를 실행한다.

 

H(P,P)의 결과가 True라면... H는 프로그램 P에 입력으로 P를 주면 정상적으로 종료된다고 말하는 것.

 

즉, P(P)는 정상적으로 종료된다고 말하는 것.

 

하지만, H(P,P)가 True이면, P(P)는 무한 루프를 돈다.

 

반대로 H(P,P)의 결과가 False라면, H는 프로그램 P에 입력으로 P를 주면 무한루프를 돈다고 말하는 것.

 

즉, P(P)는 무한루프를 돈다고 판단하는 것.

 

하지만, H(P,P)가 False이면, P(P)는 정상적으로 종료된다.

 

따라서 H는 True라고 해도 모순이고, False라고 해도 모순이다.

 

그러므로 프로그램 H는 존재하지 않는다.

 

이를 정지 문제(Halting problem)라고 부르고, 천재 컴퓨터 과학자 앨런 튜링이 이를 증명했다.

 

"어떤 주어진 프로그램이 해결하고자 하는 문제가 실제로 해결가능한가?를 말해주는 일반화된 알고리즘은 존재하지 않는다."

 

 

2. 결정 불가능한 문제(undecidable problem)

 

결정 문제는 답이 예/아니오로 판단할 수 있는 문제이다.

 

주어진 숫자 n은 소수인가? 

 

주어진 배열은 오름차순으로 정렬되어 있는가?

 

컴퓨터는 시간이 좀 걸리더라도, 유한한 시간 내에 반드시 이 문제에 대해 예나 아니오로 답할 수 있다.

 

이런 문제를 결정 문제(decision problem)라고 부른다.

 

 

그 반대로 결정 불가능한 문제는, 유한한 시간 내에 예/아니오로 답하는 알고리즘이 존재하지 않는 문제이다.

 

컴퓨터 성능이 안좋아서 그런 알고리즘이 발견되지 않은 것이 아니라, 수학적으로 그러한 알고리즘이 존재하지 않는다는 것이다.

 

 

정지 문제(halting problem)은 논리학적으로 결정 불가능함(undecidable)이 증명된 최초의 문제이다.

 

정지 문제가 증명되면서 아무리 성능이 좋은 컴퓨터가 나온다고 하더라도, 계산 능력이 부족한 것이 아니라 수학적으로 해결 불가능한 문제가 존재한다는 것을 알 수 있다.

 

또한 모든 프로그램의 모든 오류를 완벽하게 찾아내는 프로그램 분석기는 존재하지 않는다.

 

프로그램 분석기는 어떤 조건에서 오류를 발생시키는지, 무한루프가 도는지, 원하는 결과가 나오는지 등등을 판단해야하는데

 

이러한 문제의 대부분은 정지 문제로 환원되며 그렇기 때문에 완벽한 프로그램 분석기는 존재하지 않는다.

 

 

3. 환원(reduction)

 

컴퓨터 과학에서 어떤 문제 A가 다른 문제 B로 환원(reduction)된다는 것은..

 

"문제 B를 해결하는 알고리즘으로 문제 A를 해결하는 것이다."

 

어떤 사람이 타임 머신을 개발했다(문제 B)고 주장한다고 해보자.

 

그러면 나는 "이번주 로또 번호를 알아와봐(문제 A)"라고 묻는다.

 

문제 A인 로또 번호 알아맞추기를 문제 B인 타임 머신 개발하기로 환원하는 것이다.

 

타임 머신을 개발하는 것으로 로또 번호를 알아맞추는 것이다.

 

만약 타임머신을 개발했다면.. >> 이번주 로또 번호를 알아맞추는 것이 가능하다.

 

실제로 이것을 보인다면, 타임머신을 개발하는데 성공했다는 것이 환원이다.

 

하지만 이번주 로또 번호를 알아맞추는 것은 해결할 수 없는 문제이다.

 

따라서 타임 머신을 개발했다는 것은 해결할 수 없는 문제이다.

 

 

현대의 어떤 문제가 결정 불가능한 문제인지 증명하는 전형적인 방법은, 이를 정지 문제로 환원하는 것이다.

 

어떤 문제 X를 해결할 수 있다고 가정하자.

 

이 X를 해결하는 알고리즘으로 정지 문제를 해결할 수 있다면 이는 모순이므로, X를 해결하는 알고리즘이 존재하지 않는것이다.

 

따라서 X는 결정 불가능한 문제가 된다.