정지 문제 (Halting Problem)
쉽게 풀면
"이 프로그램 코드를 보기만 하고, 실행해보지 않고도 언젠가 멈추는지 아니면 무한히 반복하는지 미리 알려주는 만능 검사기를 만들 수 있을까?"라는 질문이 정지 문제입니다. 앨런 튜링은 1936년에 그런 만능 검사기는 절대로 만들 수 없다는 것을 수학적으로 증명했습니다.
간단한 프로그램 몇 개는 코드만 보고도 멈출지 알 수 있지만, "모든" 프로그램에 대해 항상 정확히 판별하는 방법은 근본적으로 존재하지 않는다는 뜻입니다. 이는 컴퓨터 성능이 부족해서가 아니라, 논리적으로 불가능하다는 한계를 보여주는 결과입니다.
왜 중요한가
정지 문제는 계산이론에서 "컴퓨터로 원리적으로 풀 수 없는 문제가 존재한다"는 사실을 보여준 초기의 대표적 사례이기 때문에, 결정 불가능성을 다루는 이후의 거의 모든 이론적 결과가 이 개념을 기준점으로 삼습니다. 소프트웨어 검증, 정적 분석, 컴파일러 최적화처럼 프로그램의 동작을 자동으로 판단하려는 실무 분야에서도, 완벽한 도구를 만들 수 없는 근본적인 이유를 설명할 때 정지 문제가 자주 인용됩니다.
핵심 정리
- 정지 문제는 “임의의 프로그램 P와 입력 x가 주어졌을 때, P가 x에서 결국 멈추는지(정지) 영원히 도는지를 항상 옳게 알려 주는 알고리즘이 있는가”라는 질문입니다. 답은 없다입니다(Turing, 1936).
- 이는 컴퓨터의 속도나 기억용량의 부족이 아니라 논리적 불가능입니다. 모든 프로그램에 대해 항상 정답을 내는 하나의 알고리즘이 불가능하다는 뜻이고, 개별 프로그램을 분석하는 일은 얼마든지 가능합니다.
- 정지하는 경우는 프로그램을 돌려 보면 언젠가 확인되지만, 정지하지 않는 경우는 ‘아직 안 멈췄다’일 뿐 확정할 수 없습니다. 그래서 정지 문제는 결정 불가능하지만 반결정 가능(인식 가능)한 문제입니다.
- 증명의 뼈대(대각선 논법): 정지 여부를 판정하는 프로그램 H가 있다고 가정하고, H가 “정지”라고 답하는 입력에서는 무한 반복하고 “무한 반복”이라고 답하는 입력에서는 멈추는 프로그램 D를 만듭니다. D를 자기 자신에게 입력하면 H의 답이 모순이 되어 H는 존재할 수 없습니다(Sipser, 2013).
- 다른 문제의 결정 불가능성은 보통 정지 문제로부터의 환원(그 문제를 풀 수 있다면 정지 문제도 풀 수 있다)으로 보입니다. Rice의 정리는 프로그램이 계산하는 함수의 자명하지 않은 성질은 모두 결정 불가능하다고 일반화합니다(Rice, 1953).
예시로 보기
| 질문 | 결정 가능한가 | 이유 |
|---|---|---|
| 프로그램 P가 입력 x에서 정지하는가(임의의 P, x) | 아니오 | 정지 문제 그 자체 |
| P가 x에서 정지하는가(특정 P, x 한 쌍) | 사람이 증명할 수도 있음 | 정답이 존재할 뿐 모든 쌍에 통하는 하나의 알고리즘이 없을 뿐 |
| P가 n단계 안에 정지하는가 | 예 | n단계까지만 실행하면 확인됨 |
| 기억 공간이 유한한 기계가 정지하는가 | 원리적으로 예 | 상태 수가 유한하므로 같은 상태가 반복되면 영원히 도는 것을 알 수 있음(실제 크기는 지수적으로 큼) |
| 두 프로그램이 같은 일을 하는가 | 아니오 | 정지 문제로부터 환원해 보일 수 있음(Rice의 정리와 같은 맥락) |
그래서 정적 분석 도구는 모든 프로그램에서 완벽할 수 없고, ‘거짓 경보를 허용하는 보수적 분석’이나 ‘종료가 증명되는 부분 집합만 허용하는 언어’처럼 타협한 설계를 택합니다.
자주 하는 오해
| 오해 | 바로잡기 |
|---|---|
| 어떤 프로그램도 멈추는지 알 수 없다. | 개별 프로그램은 분석·증명할 수 있고, 많은 도구가 종료를 증명합니다. 불가능한 것은 모든 경우에 통하는 단일 알고리즘입니다. |
| 더 빠른 컴퓨터나 인공지능이 나오면 풀린다. | 계산 능력이 아니라 논리적 한계이므로 자원이 아무리 늘어도 같습니다. |
| 튜링 기계에서만 성립한다. | 튜링 기계와 같은 계산 능력을 가진 모형(람다 계산 등)에 모두 성립합니다. 다만 ‘현실 컴퓨터는 유한하니 결정 가능’이라는 반론은 상태 수가 천문학적이라는 이유로 실용적 의미가 없습니다. |
| 정지 문제는 결정 불가능성의 최초 사례다. | 괴델의 불완전성 정리(1931)와 Church의 결과(1936)도 비슷한 시기의 결정 불가능성 결과입니다. 정지 문제는 가장 직관적이고 대표적인 사례로 자주 인용됩니다. |
논문에서는 이렇게 쓰입니다
실제 논문에서
이 용어를 직접 쓴 국내 논문 문장을 아직 수집하지 못했습니다. 수집되는 대로 출처와 함께 싣겠습니다.
예시 문장
아래는 용어의 쓰임을 보여 주려고 만든 예시로, 실제 논문에서 가져온 문장이 아닙니다.
이 문장은 "코드 분석 도구가 아무리 정교해져도, 모든 무한 루프를 빠짐없이 찾아내는 것은 도구의 완성도 문제가 아니라 이론적으로 불가능한 일"이라는 뜻입니다.
프로그래밍 언어 이론 논문에서는 완벽한 판별이 불가능하다는 사실을 인정한 뒤, 그 대신 안전하게 확인 가능한 더 좁은 범위만 다루도록 시스템을 설계했다는 뜻으로 쓰입니다.
이론전산학 논문에서는 새로운 문제가 풀 수 없음을 보이기 위해, 그 문제를 풀 수 있다면 정지 문제도 풀 수 있게 된다는 논리로 환원 증명을 구성하는 경우가 흔합니다.
조금 더 깊게 보면
정지 문제가 풀릴 수 없다는 증명은 흔히 대각선 논법을 이용하는데, 만약 정지 여부를 항상 정확히 판별하는 프로그램이 존재한다고 가정하면 자기 자신에게 모순되는 동작을 하는 프로그램을 만들 수 있음을 보여 귀류법으로 결론을 이끌어냅니다.
이 개념은 이후 다른 문제가 풀 수 없음을 보이는 표준적인 방법인 "환원(reduction)"의 출발점이 되었으며, 많은 결정 불가능성 증명이 "이 문제를 풀 수 있다면 정지 문제도 풀 수 있다"는 논리 구조를 따릅니다.
다만 결정 불가능성은 "모든 프로그램에 대해 항상 정확한 하나의 알고리즘이 없다"는 뜻이지, 개별 프로그램 하나하나를 분석하는 것 자체가 불가능하다는 뜻은 아닙니다.
주의할 점
정지 문제가 "결정 불가능(undecidable)"하다는 것은 "특정 프로그램이 멈추는지 확인할 수 없다"는 뜻이 아닙니다. 개별 프로그램은 대부분 분석해서 답을 낼 수 있습니다. 불가능한 것은 "어떤 프로그램을 넣어도 항상 정확하게 답하는 하나의 범용 알고리즘"을 만드는 일입니다. 이 개념은 계산 모델의 한계를 정의하는 튜링 기계 이론과 함께 이해하면 좋습니다.
헷갈리기 쉬운 용어
계산 가능성 이론의 용어는 이름이 서로 닮았습니다.
| 용어 | 뜻 | 정지 문제와의 관계 |
|---|---|---|
| 정지 문제 | 임의의 프로그램이 정지하는지 판정하는 문제 | — |
| 결정 가능성 | 항상 종료하며 옳은 예/아니오를 내는 알고리즘이 있는가 | 정지 문제는 결정 불가능한 대표 사례 |
| 결정 불가능 문제 | 그런 알고리즘이 없는 문제 | 정지 문제가 그 한 예 |
| 튜링 기계 | 계산을 정의하는 수학 모형 | 정지 문제는 이 모형 위에서 정식화됨 |
참고 문헌
- Turing, A. M. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, s2-42, 230–265.
- Rice, H. G. (1953). Classes of recursively enumerable sets and their decision problems. Transactions of the American Mathematical Society, 74(2), 358–366.
- Davis, M. (1958). Computability and Unsolvability. McGraw-Hill.
- Sipser, M. (2013). Introduction to the Theory of Computation (3rd ed.). Cengage Learning.
표의 기준값은 위 문헌에 근거한 관례이며, 분야·학술지마다 다른 기준을 쓸 수 있습니다.