[CS] 정지문제 (Halting problem)

정지문제 (Halting problem)

정지문제는 처음으로 증명된 판정불가능한 문제가 되었다고 한다. 정지문제를 간단하게 요약해보면 아래와 같다.

프로그램과 입력값이 주어졌을 때, 프로그램에 입력값을 넣고 실행한다면 프로그램이 계산을 끝내고 멈출지, 무한으로 계산할지 판정할수 있는가?

 

1936년에 앨런 튜링은 모든 입력값에 대해 정지문제를 풀 수 있는 일반적인 알고리즘은 존재하지 않는다는 것을 증명했다.

 

간단한 증명

귀류법을 사용하면 간단한데, 프로그램 a와 문자열 i입력으로 실행이 끝나면 true, 실행이 멈추지 않고 영원히 계산된다면 false가 결과값으로 나오는 halt(a, i)라는 알고리즘이 있다고 해보자. 이러한 완벽한 알고리즘을 가지고 아래의 함수를 구현했다고 한다면, 만약 trouble(trouble)은 결과값을 내놓을까 멈추지 않을까? 

func trouble(_ s: String) -> Bool {
    if !halt(s, s) { return true }
    return trouble(s)
}

 

1. trouble(trouble)이 계산을 끝냈다는 소리는 halt(trouble, trouble)이 false라는 것인데 이는 trouble이라는 프로그램이 영원히 계산된다는 것이기 때문에 모순이 된다.

2. trouble(trouble)이 무한하게 계산된다면 halt(trouble, trouble)이 true라는 것인데 이는 trouble이라는 프로그램이 실행이 끝난다는 것을 의미하기 때문에 모순이 된다.

 

어떤경우에도 halt(a, i)는 올바른 답을 내놓을 수 없다. 따라서 halt(a, i)는 존재하지 않는다. 결국 문제가 풀릴지 안풀릴지 판단하는 완벽한 알고리즘은 존재하지 않는다. 이 뜻은 결국 아무리 컴퓨터가 발전해도 모든것을 해낼 수는 없다는 것을 의미한다.

 

아래는 튜링머신을 통해 정지문제를 증명한 유튜브 영상이다.

출처: https://www.youtube.com/watch?v=92WHN-pAFCs