정지 문제 (Halting problem)

정지 문제란?

임의의 튜링 머신에 유한한 상태를 거쳤을 때, 이 튜링 머신이 정지 상태로 가는지 아닌지를 판별 할 수 있는 알고리즘이 존재할까?

 

결론부터 말하자면 이러한 알고리즘은 존재하지 않으며, 이는 귀류법으로 증명할 수 있다. 튜링 머신은 하나의 프로그램으로 생각할 수 있으므로, 이를 함수로 바꿔서 생각해보기로 했다.

 

귀류법을 사용하기 위해, 다음과 같은 가정을 해보자.

 

어떤 함수가 특정 입력값에 대해 무한 루프에 빠지는지 아닌지를 판별할 수 있는 함수 H가 존재한다.

이와 같은 가정에 모순이 생긴다면, 귀류법에 의해 이러한 함수는 존재하지 않는다는 것을 증명할 수 있다.

 

함수 H(F, I)를 정의하자. F는 판별 대상 함수, I는 입력값이고, 함수 F가 I를 입력받았을 때 정상적으로 종료된다면 true, 무한 루프에 빠진다면 false를 리턴한다.

판별 대상 함수는 아래와 같다고 가정해보자. 간단하게 파이썬을 이용해서 작성했다.

 

def F(I):
    while H(I, I):
        print("loop!")
    return "end!"

 

이 함수에 입력값으로 F를 넣는다고 가정해보자. 그러면 이 함수는 H(F, F)의 값에 따라서 무한 루프에 빠질지, 정상적으로 종료될지가 결정된다.

H(F, F)의 값이 어떻게 나올지는 잘 모르겠지만, true일 때와 false일 때로 경우를 나눠서 생각해보자.

 

1. H(F, F) == true

  이 경우 F(F)는 무한 루프에 빠진다. 그렇다면 H(F, F)의 값은 false가 되어야 하지만, H(F, F)가 true라고 가정했으므로 이는 모순이 된다.

 

2. H(F, F) == false

  이 경우 F(F)는 정상적으로 종료되고, H(F, F)는 true가 되어야 한다. 그런데 H(F, F)가 false라고 가정했으므로 H(F, F)가 true일 때와 마찬가지로 모순이 된다.

 

따라서 H(F, F)가 어떤 값을 리턴하더라도 모순이 생기게 된다. 따라서 귀류법에 따라 이러한 함수 H는 존재하지 않는다는 것을 알 수 있다.