3.17 정지 문제(Halting Problem)의 정의

1. 정지 문제의 직관적 기술

정지 문제(Halting Problem)는 다음의 질문으로 직관적으로 기술된다:

임의의 컴퓨터 프로그램과 그 프로그램에 대한 입력이 주어졌을 때, 해당 프로그램이 해당 입력에 대해 유한 시간 내에 종료(정지)하는지, 아니면 영원히 실행을 계속하는지를 판별하는 일반적 알고리즘이 존재하는가?

이 질문에 대한 답변은 부정적(Negative)이다. 튜링(Alan Turing)은 1936년 이러한 일반적 알고리즘이 존재하지 않음을 증명하였으며, 이 결과는 계산 이론에서 가장 근본적인 부정적 결과 중 하나이다.

2. 정지 문제의 형식적 정의

2.1 언어 형식

정지 문제를 언어(Language)의 판별 문제로 정식화한다. 다음의 언어 $\text{HALT}$ 를 정의한다:

$\text{HALT} = \{\langle M, w \rangle \mid M \text{은 튜링 기계이고, } M \text{이 입력 } w \text{에 대해 정지한다}\}$

여기서 $\langle M, w \rangle$ 는 튜링 기계 $M$ 의 부호화(Encoding)와 입력 문자열 $w$ 를 결합한 문자열이다.

정지 문제의 질문은 다음과 동치이다: 언어 $\text{HALT}$ 는 결정 가능(Decidable, 또는 재귀적, Recursive)한가? 즉, 임의의 $\langle M, w \rangle$ 에 대해 $\langle M, w \rangle \in \text{HALT}$ 인지 아닌지를 항상 올바르게 판정하고 정지하는 튜링 기계(결정기, Decider)가 존재하는가?

함수 형식

동등하게, 다음의 함수 $\text{halt}: \Sigma^* \times \Sigma^* \rightarrow \{0, 1\}$ 을 정의한다:

$\text{halt}(M, w) = \begin{cases} 1 & \text{if } M \text{ halts on } w \\ 0 & \text{if } M \text{ does not halt on } w \end{cases}$

정지 문제는 이 함수가 계산 가능(Computable)한지를 묻는 것이다.

3. “정지“의 정밀한 의미

튜링 기계 $M$ 이 입력 $w$ 에 대해 정지한다(Halt) 함은, $M$ 의 계산이 유한 단계 후에 종료됨을 의미한다. 구체적으로, $M$ 이 수락 상태 $q_{\text{accept}}$ 또는 거부 상태 $q_{\text{reject}}$ 에 도달하는 것이다.

$M$ 이 $w$ 에 대해 정지하지 않는다(Does Not Halt) 함은, $M$ 의 계산이 무한히 계속됨을 의미한다. 즉, $M$ 이 수락 상태나 거부 상태에 결코 도달하지 않고, 전이를 무한히 반복한다.

4. 정지 문제의 구별

정지 문제를 관련된 다른 결정 문제와 구별하는 것이 중요하다.

4.1 수락 문제(Acceptance Problem)

$A_{\text{TM}} = \{\langle M, w \rangle \mid M \text{은 튜링 기계이고, } M \text{이 입력 } w \text{를 수락한다}\}$

수락 문제는 $M$ 이 $w$ 를 수락하는지를 묻는다. 정지 문제는 $M$ 이 $w$ 에 대해 정지하는지(수락 또는 거부)를 묻는다.

수락 문제도 결정 불가능하지만, 인식 가능(Recognizable)하다. 보편 튜링 기계가 $M$ 을 $w$ 에 대해 시뮬레이션하면, $M$ 이 수락할 경우 이를 탐지할 수 있다. 그러나 $M$ 이 정지하지 않는 경우 이를 탐지할 수 없다.

자기 정지 문제(Self-Halting Problem)

$\text{SELF-HALT} = \{\langle M \rangle \mid M \text{은 튜링 기계이고, } M \text{이 입력 } \langle M \rangle \text{에 대해 정지한다}\}$

자기 정지 문제는 튜링 기계가 자기 자신의 부호화를 입력으로 받을 때 정지하는지를 묻는다. 정지 문제의 결정 불가능성 증명에서 이 특수한 경우가 핵심적 역할을 한다.

5. 정지 문제의 인식 가능성

정지 문제의 언어 $\text{HALT}$ 는 인식 가능(Recognizable)하다. 이를 인식하는 튜링 기계 $R$ 의 구성:

입력 $\langle M, w \rangle$ 를 받는다.
보편 튜링 기계를 사용하여 $M$ 을 $w$ 에 대해 시뮬레이션한다.
$M$ 이 정지하면(수락 또는 거부), $R$ 은 수락한다.

$M$ 이 정지하면 $R$ 은 유한 시간 후에 수락하므로, $R$ 은 $\text{HALT}$ 를 인식한다. 그러나 $M$ 이 정지하지 않으면 $R$ 도 정지하지 않으므로, $R$ 은 결정기가 아니다.

6. 정지 문제의 보수(Complement)

정지 문제의 보수는 다음의 언어이다:

$\overline{\text{HALT}} = \{\langle M, w \rangle \mid M \text{은 튜링 기계가 아니거나, } M \text{이 입력 } w \text{에 대해 정지하지 않는다}\}$

$\text{HALT}$ 가 인식 가능하지만 결정 불가능하므로, $\overline{\text{HALT}}$ 는 인식 불가능(Not Recognizable)하다. 이는 다음의 정리에 기반한다:

정리: 언어 $L$ 이 결정 가능한 것은 $L$ 과 $\overline{L}$ 이 모두 인식 가능한 것과 동치이다.

$\text{HALT}$ 가 인식 가능하고 $\overline{\text{HALT}}$ 도 인식 가능하다면, $\text{HALT}$ 는 결정 가능해야 하지만 결정 불가능하므로 모순이다. 따라서 $\overline{\text{HALT}}$ 는 인식 불가능하다.

정지 문제의 실용적 의의

정지 문제의 결정 불가능성은 다음의 실용적 함의를 갖는다.

첫째, 완벽한 프로그램 검증기(Program Verifier)의 불가능성: 임의의 프로그램이 주어진 입력에 대해 종료하는지를 자동으로 판별하는 범용적 도구를 구축하는 것은 원리적으로 불가능하다. 정적 분석(Static Analysis)과 형식 검증(Formal Verification) 도구는 특정 프로그램 클래스에 대해 정지 여부를 판별할 수 있으나, 모든 프로그램에 대해 작동하는 범용 도구는 존재하지 않는다.

둘째, 완벽한 바이러스 탐지기의 불가능성: 임의의 프로그램이 악성(Malicious) 행동을 수행하는지를 일반적으로 판별하는 것은 정지 문제로 환원 가능하며, 따라서 결정 불가능하다.

셋째, 최적화의 근본적 한계: 임의의 프로그램을 최적화하여 더 빠르거나 더 적은 공간을 사용하는 동등한 프로그램을 생성하는 것은 일반적으로 결정 불가능하다(라이스의 정리, Rice’s Theorem의 귀결).

정지 문제는 계산의 근본적 한계를 보여주는 가장 기본적인 결정 불가능 문제이며, 계산 이론의 핵심 결과이다.