정지 문제

정지 문제는 임의의 컴퓨터 프로그램과 그 프로그램에 들어갈 입력값이 주어졌을 때, 이 프로그램이 실행을 마친 후 정지할 것인지 아니면 무한히 실행될 것인지를 미리 알아낼 수 있는지를 묻는다. 앨런 튜링은 튜링 기계를 통해 이 문제를 분석하였으며, 어떠한 단일 알고리즘으로도 모든 프로그램의 정지 여부를 판정할 수 없음을 밝혀냈다. 이를 '정지 문제는 튜링 기계에서 판정할 수 없다'고 표현한다.

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

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

이러한 모순에 따라 정지 여부를 완벽히 판정하는 프로그램 $H$는 존재할 수 없다.

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