정지 문제

정지 문제는 임의의 컴퓨터 프로그램과 그 프로그램에 들어갈 입력값이 주어졌을 때, 이 프로그램이 실행을 마친 후 정지할 것인지 아니면 무한히 실행될 것인지를 미리 알아낼 수 있는지를 묻는다. 모든 프로그램은 실행 시 유한한 절차를 거쳐 결과를 내놓거나, 혹은 무한 루프에 빠져 종료되지 않는 두 가지 상태 중 하나에 놓인다. 앨런 튜링은 튜링 기계를 통해 이 문제를 분석하였으며, 어떠한 단일 알고리즘으로도 모든 프로그램의 정지 여부를 판정할 수 없음을 밝혀냈다. 이를 '정지 문제는 튜링 기계에서 판정할 수 없다'고 표현한다.

정지 문제의 판정 불가능성은 1936년 앨런 튜링에 의해 처음으로 증명되었다. 비슷한 시기인 1936년 4월, 알론조 처치 또한 람다 셈법을 이용하여 판정 불가능한 문제가 존재함을 독립적으로 증명하였다. 튜링의 증명은 같은 해 5월에 출판되었으며, 현대적인 컴퓨터의 모델인 튜링 기계 개념을 도입하여 문제를 정형화했다는 점에서 큰 의의를 갖는다. '정지(Halting)'라는 용어는 튜링이 직접 사용한 것은 아니며, 1950년대 마틴 데이비스의 연구를 통해 널리 보급된 것으로 알려져 있다.

정지 문제의 불가능성은 귀류법을 통해 증명된다. 만약 모든 프로그램의 정지 여부를 판정할 수 있는 프로그램 $H$가 존재한다고 가정하면 다음과 같은 모순이 발생한다.

1. 프로그램 $H(P, I)$는 프로그램 $P$에 입력 $I$를 넣었을 때 정지하면 '참', 정지하지 않으면 '거짓'을 반환한다.
2. $H$를 이용해 새로운 프로그램 $S$를 설계한다. $S$는 $H(P, P)$가 '참'을 반환하면 무한 루프를 돌고, '거짓'을 반환하면 즉시 정지한다.
3. 이제 $S$에 자기 자신인 $S$를 입력으로 넣는 경우($S(S)$)를 가정한다.
4. 만약 $S(S)$가 정지한다면 $H(S, S)$는 '참'을 반환해야 하고, 설계에 따라 $S$는 무한 루프를 돌아야 하므로 모순이다.
5. 반대로 $S(S)$가 정지하지 않는다면 $H(S, S)$는 '거짓'을 반환해야 하고, 설계에 따라 $S$는 정지해야 하므로 역시 모순이다.

이러한 논리적 모순에 따라 모든 경우를 완벽히 판정하는 프로그램 $H$는 존재할 수 없다.

정지 문제는 역사상 처음으로 컴퓨터로 해결할 수 없는 문제가 존재함을 증명한 사례이다. 이는 인간의 사고나 수학적 증명 과정이 기계적인 계산으로 모두 대체될 수 있는지에 대한 질문에 중요한 답을 제시하였다. 또한 계산 가능성 이론의 기초가 되었으며, 현대 컴퓨터 과학에서 알고리즘의 한계를 규정하는 핵심적인 원리로 작용한다. 실무적으로는 컴파일러의 최적화나 프로그램의 오류 검증, 보안 분석 등에서 모든 버그나 무한 루프를 자동으로 찾아내는 도구를 만드는 것이 이론적으로 불가능함을 시사한다.

정지 문제의 판정 불가능성이 증명된 이후, 수많은 다른 문제들도 판정 불가능함이 밝혀졌다. 이를 증명하기 위해 '환원(Reduction)'이라는 기법이 사용된다. 환원은 새로운 문제 $B$를 해결할 수 있는 방법이 있다면, 이를 이용해 이미 판정 불가능함이 증명된 정지 문제 $A$를 해결할 수 있음을 보이는 방식이다. 만약 $B$를 통해 $A$를 풀 수 있다면, $A$가 판정 불가능하므로 $B$ 역시 판정 불가능하다는 결론에 도달하게 된다.