3.19 결정 가능 언어와 인식 가능 언어의 분류

1. 언어의 계층적 분류

계산 이론에서 형식 언어(Formal Language)는 그 계산적 복잡도에 따라 계층적으로 분류된다. 가장 근본적인 분류는 튜링 기계에 의한 결정 가능성(Decidability)과 인식 가능성(Recognizability)에 기반한다.

2. 결정 가능 언어(Decidable Language)

2.1 정의

언어 $L \subseteq \Sigma^*$ 이 결정 가능(Decidable)하다 함은, $L$ 을 결정하는 튜링 기계(결정기, Decider) $M$ 이 존재함을 의미한다. 결정기 $M$ 은 다음의 두 조건을 만족한다:

정지성(Halting): 모든 입력 $w \in \Sigma^*$ 에 대해 $M$ 이 정지한다. 즉, $M$ 은 모든 입력을 수락 또는 거부하며, 무한 루프에 빠지지 않는다.
정확성(Correctness): $w \in L$ 이면 $M$ 이 $w$ 를 수락하고, $w \notin L$ 이면 $M$ 이 $w$ 를 거부한다.

결정 가능 언어는 재귀 언어(Recursive Language)라고도 불린다.

2.2 결정 가능 언어의 예

유한 언어(Finite Language): 원소의 수가 유한한 모든 언어는 결정 가능하다.
정규 언어(Regular Language): 유한 오토마타(Finite Automaton)에 의해 인식되는 모든 언어는 결정 가능하다.
문맥 자유 언어(Context-Free Language): 문맥 자유 문법(Context-Free Grammar)에 의해 생성되는 모든 언어는 결정 가능하다.
$\{0^n 1^n \mid n \geq 0\}$ : 0의 수와 1의 수가 같은 문자열의 언어.
$\{ww^R \mid w \in \{0,1\}^*\}$ : 회문(Palindrome)의 언어.

3. 인식 가능 언어(Recognizable Language)

3.1 정의

언어 $L \subseteq \Sigma^*$ 이 인식 가능(Recognizable)하다 함은, $L$ 을 인식하는 튜링 기계 $M$ 이 존재함을 의미한다. 즉:

$w \in L$ 이면 $M$ 이 $w$ 를 수락한다.
$w \notin L$ 이면 $M$ 이 $w$ 를 거부하거나 정지하지 않는다.

인식 가능 언어는 재귀적으로 열거 가능한 언어(Recursively Enumerable Language, RE)라고도 불린다. “재귀적으로 열거 가능“이라는 명칭은 이 언어의 원소를 열거하는 튜링 기계가 존재한다는 동치적 특성화에서 유래한다.

3.2 인식 가능하지만 결정 불가능한 언어의 예

$\text{HALT} = \{\langle M, w \rangle \mid M \text{이 } w \text{에 대해 정지한다}\}$ : 정지 문제의 언어.
$A_{\text{TM}} = \{\langle M, w \rangle \mid M \text{이 } w \text{를 수락한다}\}$ : 수락 문제의 언어.

4. 인식 불가능 언어

4.1 정의

어떤 튜링 기계도 인식하지 못하는 언어를 인식 불가능(Not Recognizable) 언어라 한다. 즉, 이 언어의 원소를 열거하거나 확인하는 알고리즘적 절차가 존재하지 않는다.

4.2 인식 불가능 언어의 예

$\overline{\text{HALT}} = \{\langle M, w \rangle \mid M \text{이 } w \text{에 대해 정지하지 않는다}\}$ : 정지 문제의 보수(Complement).
$\overline{A_{\text{TM}}} = \{\langle M, w \rangle \mid M \text{이 } w \text{를 수락하지 않는다}\}$ : 수락 문제의 보수.

5. 세 범주의 관계

$\text{결정 가능 언어} \subsetneq \text{인식 가능 언어} \subsetneq \text{모든 언어}$

이 포함 관계의 엄격성(Strict Inclusion):

결정 가능 $\subsetneq$ 인식 가능: $\text{HALT}$ 는 인식 가능하지만 결정 불가능하다.
인식 가능 $\subsetneq$ 모든 언어: $\overline{\text{HALT}}$ 는 인식 불가능하다.

핵심 정리: 결정 가능성의 특성화

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

$L \text{ decidable} \iff L \text{ recognizable} \wedge \overline{L} \text{ recognizable}$

5.1 증명

( $\Rightarrow$ ): $L$ 이 결정 가능하면, $L$ 을 결정하는 결정기 $M$ 이 존재한다. $M$ 은 $L$ 을 인식하므로 $L$ 은 인식 가능하다. $M$ 의 수락과 거부를 교환한 기계 $M'$ 는 $\overline{L}$ 을 결정하므로, $\overline{L}$ 도 인식 가능하다.

( $\Leftarrow$ ): $L$ 을 인식하는 튜링 기계 $M_1$ 과 $\overline{L}$ 을 인식하는 튜링 기계 $M_2$ 가 존재한다고 하자. 새로운 기계 $M$ 을 다음과 같이 구성한다: 입력 $w$ 에 대해 $M_1$ 과 $M_2$ 를 교대로(Alternately) 한 단계씩 시뮬레이션한다. $M_1$ 이 수락하면 $M$ 은 수락하고, $M_2$ 가 수락하면 $M$ 은 거부한다. $w \in L$ 이면 $M_1$ 이 유한 단계 후 수락하고, $w \notin L$ 이면 $M_2$ 가 유한 단계 후 수락하므로, $M$ 은 모든 입력에 대해 정지한다. 따라서 $M$ 은 $L$ 의 결정기이다.

6. 촘스키 위계와의 관계

계산 이론에서의 언어 분류는 촘스키 위계(Chomsky Hierarchy)와 밀접하게 연관된다:

문법 유형	언어 클래스	인식 기계	계산적 분류
유형 3 (정규)	정규 언어	유한 오토마타	결정 가능
유형 2 (문맥 자유)	문맥 자유 언어	푸시다운 오토마타	결정 가능
유형 1 (문맥 의존)	문맥 의존 언어	선형 유계 오토마타	결정 가능
유형 0 (제한 없음)	RE 언어	튜링 기계	인식 가능

모든 결정 가능 언어는 유형 0에 포함되지만, 유형 0 언어 중 결정 불가능한 것이 존재한다(예: $\text{HALT}$ ).

7. 분류의 이론적 의의

결정 가능 언어와 인식 가능 언어의 분류는 계산 이론의 근간을 이루며, 다음의 근본적 물음에 대한 정밀한 답변을 제공한다:

무엇이 알고리즘적으로 해결 가능한가? → 결정 가능 문제의 범위
무엇이 부분적으로나마 알고리즘적으로 확인 가능한가? → 인식 가능 문제의 범위
무엇이 알고리즘적 접근 자체가 불가능한가? → 인식 불가능 문제의 범위

이 분류는 인공지능의 원리적 능력과 한계를 규정하는 이론적 기반이다. 인공지능 체계는 튜링 기계로 구현되므로, 결정 불가능한 문제는 인공지능에 의해서도 일반적으로 해결될 수 없다.