정지 문제

계산 복잡도 이론에서 정지문제(停止問題, halting problem)는 판정 문제의 일종으로 다음과 같이 요약할 수 있다.

프로그램을 설명한 것과 처음 입력값이 주어졌을 때, 이 프로그램에 입력값을 넣고 실행한다면 이 프로그램이 계산을 끝내고 멈출지 아니면 영원히 계속 계산할지 판정하라.

1936년에 앨런 튜링이 모든 가능한 입력값에 대해 정지문제를 풀 수 있는 일반적인 알고리즘은 존재하지 않는다는 것을 증명했다. 그러므로 '정지문제는 튜링 기계에서 판정할 수 없다'고 한다.

정지문제의 중요성과 의미

정지문제는 처음으로 증명된 판정불가능한 문제라는 점에서 역사적으로 중요한 의미를 갖는다. (튜링의 증명은 1936년 5월에 출판되었으나, 알론조 처치는 1936년 4월에 람다 셈법을 이용하여 판정불가능한 문제가 존재함을 증명하였다.) 이 문제 이후로, 수많은 문제들도 비슷한 방법으로 판정불가능함을 증명했다. 판정불가능하다는 것을 보이기 위해서 환원이라는 방법을 사용한다. 환원이라는 것은 '새로운 문제를 판정하는 방법이 있다면, 기존의 판정불가능한 문제의 모든 경우를 새로운 문제의 경우로 변환시켜서 기존의 판정불가능한 문제를 판정할 수 있다'는 것을 보이는 것이다. 한편 어떻게 하더라도 '예전' 문제를 풀 수 없기 때문에, 새로운 문제 역시 풀 수 없다. 이와 같은 과정으로 새로운 문제 역시 판정불가능하다는 것을 보이는 것이다.

개략적인 증명

증명은 귀류법(proof by contradiction)을 이용한다. 우선 모든 프로그램을 최소한 하나의 문자열과 연관시킬 수 있는 프로그래밍 언어를 고르자. 임의의 문자열 i와 임의의 프로그램을 나타내는 문자열 a에 대해, i라는 문자열을 입력으로 프로그램 a을 실행했을 경우를 계산하여, 그 실행이 끝나면 true, 끝나지 않고 영원히 계속되면 false를 반환하는 halt(a, i)란 알고리즘이 있다고 누군가 주장한다고 하자. 이때 다음과 같이 trouble이라는 서브루틴을 만들어 보았다고 하면,

 function trouble(string s)
     if halt(s, s) == false
         return true
     else
         loop forever

이 프로그램은 프로그램을 나타내는 문자열 s를 인자로 받아 s를 halt의 두 인자(프로그램과 초기 문자열)로 주어 실행하고, halt가 false를 반환하면 true를 반환하고, 그렇지 않으면 무한 루프로 빠져버리는 프로그램이다. 모든 프로그램은 어떤 문자열인가로 표현될 수 있기 때문에, 어떤 문자열 t는 이 프로그램 trouble을 나타낼 것이다. 이 t라는 문자열을 이 프로그램에 넣어 돌린 trouble(t)는 과연 반환값을 내놓을까, 아니면 영원히 멈추지 않을까?

두 가지 경우를 모두 고려해 보면 다음과 같다.

1. 만약 trouble(t)가 계산을 끝낸다고 하면, 그건 분명히 halt(t, t)가 반환값으로 false를 내놓기 때문이다. 그러나, 그것은 다시 trouble(t)가 멈추지 않고 영원히 지속된다는 말이다.
2. 만약 trouble(t)이 무한히 돈다면, 그것은 halt가 영원히 계산을 끝내지 않거나, halt가 true를 반환하기 때문이다. 이것은 다시 halt 가 임의의 문자열과 프로그램에 대해 판정할 수 없거나, trouble(t)가 계산 끝내고 멈춘다는 결론을 이끌어낸다.

어떤 경우에도 halt는 옳은 답을 내놓지 못하여, 처음의 주장과 모순을 일으킨다. 이 논리는 정지문제에 대한 답으로 제시되는 모든 프로그램에 적용될 수 있기 때문에, 이 문제에 대한 해답은 있을 수 없다.

이 고전적인 증명은 보통 대각선 논법으로 불리는데, 왜냐하면, halt(a, i)의 값을 a를 행으로, i를 열로 갖는 격자에 쭉 배열하였을 때 halt(s, s)는 이 격자의 대각선에 해당하기 때문이다. 이런 격자를 상상했을 때 증명은 "문자열 t에 해당하는 행이 어디인가?"란 질문과 그 답으로 대체될 수 있다. 질문에 대한 답은 trouble 함수가 t를 격자 배열의 어느 행으로 선택하더라도 halt(t, i)값이 최소한 대각선의 위치인 halt(t, t)에서는 맞지 않도록 고안되었으며, 따라서 격자가 임의의 a에 대한 행을 포함해야 한다는 조건과 모순을 일으키며, 정지문제는 판정불가능이 된다.

같이 보기

• 바쁜 비버
• 콜모고로프 복잡도
• P-NP 문제

참고 문헌

• 앨런 튜링, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, 42 (1936), pp 230–265. online version 이 논문은 튜링이 튜링 기계, 정지 문제 등을 정의하는 역사적인 논문이다. 튜링은 여기서 정지 문제가 Entscheidungsproblem과 마찬가지로 푸는 것이 불가능한 문제라는 것을 보인다.
• Church, Alonzo; Rosser, J. Barkley (May 1936), “Some properties of conversion”, 《Transactions of the American Mathematical Society》 39 (3): 472–482, JSTOR 1989762 .