강의 8

결정 불가능성

알고리즘이 풀 수 없는 첫 번째 문제 — 그리고 그것이 왜 피할 수 없는 운명인가.

1. 무대 설정: 가산과 비가산

결정 불가능한 문제가 존재한다는 사실의 가장 우아한 증명은 단 한 줄짜리 개수 세기다. "알고리즘은 가산(countable)이다. 그러나 언어는 비가산(uncountable)이다. 그러므로 알고리즘이 짝지어줄 수 없는 언어가 — 사실은 거의 모든 언어가 — 존재한다." 이 직관을 정리해두자.

정의 8.1. 집합 S가 가산이라 함은, S가 유한하거나 자연수 집합 ℕ과 일대일 대응(전단사, bijection)이 있다는 뜻이다. 그렇지 않으면 S는 비가산이다.

예제 8.2. ℤ는 0, 1, −1, 2, −2, … 의 순서로 ℕ과 일대일 대응되므로 가산이다. ℚ도 분수를 행렬처럼 나열한 뒤 대각선 순회하면 가산임을 보일 수 있다. 유한 알파벳 Σ에 대한 모든 문자열의 집합 Σ* 또한 가산이다 — 길이순, 같은 길이 안에서는 사전식으로 나열하면 된다.

정리 8.3 (칸토어). 실수의 집합 ℝ은 비가산이다. 더 일반적으로, 임의의 무한 집합 X의 멱집합 𝒫(X)는 X와 일대일 대응될 수 없다.

증명 스케치 (대각선 논법). ℝ의 부분 집합 [0, 1)이 가산이라고 가정하자. 그러면 그 안의 모든 수를 r₁, r₂, r₃, … 으로 나열할 수 있고, 각 r_i의 십진 전개를 r_i = 0.d_i,1d_i,2d_i,3… 으로 적는다. 이제 새 수 x = 0.e₁e₂… 를 정의하자. 단, e_i ≠ d_i,i이고 e_i ∈ {3, 5}로 잡자(애매한 0.999… = 1.000… 같은 사례를 피하기 위해). 그러면 x는 모든 r_i와 적어도 i번째 자리에서 다르므로 어떤 r_i와도 같지 않다. 그러나 x ∈ [0, 1)이므로 우리의 나열에 포함되어야 한다 — 모순. ∎

이 한 번의 대각선화를 우리는 이 강의에서 두 번 더 본다. 형태는 늘 같다: "모든 후보가 나열되었다고 가정하고, 그 나열의 대각선을 비틀어 새로운 대상을 만들어 모순을 일으킨다."

2. 인식 불가능 언어의 존재

이제 위 정리를 계산이론으로 옮긴다.

정리 8.4. 알파벳 Σ가 비어 있지 않을 때, 인식 불가능한(non-Turing-recognizable) 언어 L ⊆ Σ*가 존재한다.

증명.

TM은 가산이다. 모든 TM은 — 합리적 인코딩 규약에서 — 어떤 유한 문자열 ⟨M⟩으로 표현된다. ⟨M⟩은 Σ*의 원소이고 Σ*는 가산이므로, TM의 집합도 가산이다. 따라서 인식 가능 언어의 집합 R_e = { L(M) : M은 TM }도 가산이다.
언어는 비가산이다. Σ*의 모든 부분 집합의 집합 𝒫(Σ*)이 곧 모든 언어의 집합이다. 정리 8.3에 의해 𝒫(Σ*)는 비가산이다.
가산 집합은 비가산 집합을 덮을 수 없으므로, 인식 가능하지 않은 언어가 존재한다. ∎

아름답지만 답답한 증명이다. "그래서 그 인식 불가능 언어가 무엇인가?"에 답하지 못한다. 다음 절에서 우리는 구체적으로 흥미로운 결정 불가능 언어를 손에 쥐게 된다.

3. A_TM: 보편 시뮬레이터의 한계

A_TM = { ⟨M, w⟩ : M은 TM이고 M이 w를 수락한다 }

정리 8.5. A_TM은 튜링 인식 가능하다.

증명. 보편 튜링 기계(universal TM) U는 입력 ⟨M, w⟩를 받아 M이 w에 대해 동작하는 모습을 한 단계씩 시뮬레이션한다. M이 수락하면 U도 수락하고, M이 거부하면 U도 거부한다. M이 멈추지 않으면 U도 멈추지 않는다 — 그러나 그것이 인식자(recognizer)의 정의에 위배되지는 않는다. 따라서 U는 A_TM을 인식한다. ∎

U의 존재가 곧 "프로그램으로서의 컴퓨터"라는 폰 노이만식 패러다임의 이론적 토대다. 그러나 U가 인식자일 뿐 결정자는 아니라는 점이 결정적이다. 다음 정리가 그 이유를 알려준다.

정리 8.6 (튜링 1936). A_TM은 결정 불가능하다.

증명 (대각선 논법). 결정자 TM H가 존재해 모든 ⟨M, w⟩에 대해

H(⟨M, w⟩) = 수락 (M이 w를 수락) / 거부 (M이 w를 거부하거나 멈추지 않음)

을 항상 멈추며 답한다고 가정한다. 우리의 목표는 모순을 도출하는 것이다.

H를 부품으로 새 TM D를 다음과 같이 정의한다.

D(⟨M⟩):

입력 ⟨M⟩을 받는다(즉, 어떤 TM의 인코딩).
H를 ⟨M, ⟨M⟩⟩에 대해 호출한다 — "기계 M이 자기 자신의 인코딩에 대해 어떻게 동작하는가?"를 묻는다.
H가 수락하면 D는 거부한다. H가 거부하면 D는 수락한다.

H가 결정자이므로 D도 결정자다. 이제 D를 자기 자신에게 적용해보자. D(⟨D⟩)는 어떤 답을 내놓을까?

D(⟨D⟩) = 수락 ⟹ H(⟨D, ⟨D⟩⟩) = 거부 ⟹ D가 ⟨D⟩를 수락하지 않는다 ⟹ D(⟨D⟩) = 거부.
D(⟨D⟩) = 거부 ⟹ H(⟨D, ⟨D⟩⟩) = 수락 ⟹ D가 ⟨D⟩를 수락한다 ⟹ D(⟨D⟩) = 수락.

두 경우 모두 모순이다. 따라서 가정한 H는 존재할 수 없다. ∎

한 줄 메모. 이것은 칸토어의 대각선 논법을 그대로 옮겨온 것이다. 실수의 자리표 d_i,i가 "기계 i가 입력 i에 대해 무엇을 하는가"로 바뀌었을 뿐, 비트는 동일한 동작을 한다. 자기 참조라는 칼날이 자기 자신을 베는 순간이다.

4. 보조정리: 인식과 여인식의 결합

다음 절로 가기 전에 작은 보조정리 하나가 필요하다. 이는 인식 가능성과 결정 가능성 사이의 다리다.

보조정리 8.7. 언어 L이 결정 가능 ⟺ L과 그 여집합 L = Σ* ∖ L이 모두 인식 가능.

증명.

(⇒) L이 결정 가능하면 결정자 M이 있어서 항상 멈추고 정확한 답을 준다. L의 인식자는 M 자신이고, L의 인식자는 M의 수락·거부를 뒤집은 M′이다. 둘 다 항상 멈추므로 인식자다.

(⇐) M₁이 L을, M₂가 L을 인식한다고 하자. 결정자 M을 다음과 같이 만든다. 입력 w에 대해 M₁과 M₂를 동시에(예: 두 테이프에서 한 단계씩 번갈아) 시뮬레이션한다. M₁이 수락하면 M도 수락한다. M₂가 수락하면 M은 거부한다. w는 L이거나 L 중 하나에 정확히 속하므로 둘 중 하나는 반드시 유한 시간 안에 수락한다. 따라서 M은 항상 멈춘다 — 결정자다. ∎

대우 형태로 읽으면 더 강력하다: L이 인식 가능이고 결정 불가능이면, L은 인식 가능조차 아니다.

5. A_TM의 여집합: 인식 불가능의 첫 사례

정리 8.8. A_TM = { ⟨M, w⟩ : M이 TM이고 M이 w를 수락하지 않는다 }은 인식 불가능하다.

증명. 정리 8.5에서 A_TM이 인식 가능임을 보았다. 정리 8.6에서 A_TM이 결정 불가능임을 보았다. 만약 A_TM도 인식 가능이라면, 보조정리 8.7에 의해 A_TM이 결정 가능해야 하므로 모순이다. 따라서 A_TM은 인식 불가능. ∎

이 정리에서 인식 가능 언어의 클래스(통상 RE 또는 R_e로 표기)는 여집합 아래에서 닫혀 있지 않다는 사실이 따라온다. 정규 언어와 결정 가능 언어와는 달리, 인식 가능 언어 한 개를 뒤집으면 클래스 밖으로 튀어나갈 수 있다. 이 비대칭이 결정 가능과 인식 가능을 가르는 가장 깊은 차이다.

한 줄 메모. 이로써 우리는 세 종류의 언어를 손에 쥔다 — 결정 가능, 인식 가능하지만 결정 불가능(A_TM), 인식 가능조차 아닌 것(A_TM). 풍경에 처음으로 깊이가 생겼다.

6. HALT_TM: 환원 기법의 첫 시연

HALT_TM = { ⟨M, w⟩ : M이 w에 대해 (수락이든 거부든) 멈춘다 }

정리 8.9. HALT_TM은 결정 불가능하다.

증명 (A_TM으로부터의 환원). HALT_TM의 결정자 R이 존재한다고 가정하자. 그러면 R을 부품으로 A_TM의 결정자 S를 만들 수 있다.

S(⟨M, w⟩):

R을 ⟨M, w⟩에 대해 호출한다.
R이 거부하면(즉 M이 w에 대해 멈추지 않음), S는 거부한다 — 멈추지 않는 기계는 수락할 수 없으므로.
R이 수락하면(즉 M이 w에 대해 멈춤), 보편 TM U로 M을 w에 대해 시뮬레이션한다. 멈춤이 보장되므로 유한 시간 안에 결과가 나온다.
U의 결과가 수락이면 S도 수락, 거부면 S도 거부한다.

S는 항상 멈추고 A_TM의 멤버십을 정확히 답한다 — 정리 8.6과 모순. 따라서 R은 존재하지 않는다. ∎

이 증명에 등장한 작은 패턴 — "B의 결정자가 있으면 A의 결정자를 만들 수 있다, 따라서 A가 결정 불가능이면 B도 결정 불가능" — 이 다음 강의의 주인공인 매핑 환원(mapping reduction)의 비공식 형태다. 환원은 결정 불가능성을 한 문제에서 다른 문제로 옮겨 심는 묘목 이식 기술이며, 우리는 이미 그 첫 한 그루를 심었다.

한 줄 메모. 컴퓨터 과학 입문 시간에 들었을 "정지 문제(halting problem)는 풀리지 않는다"는 바로 이 정리 8.9를 말한다. 단, 보다 정확히 하자면 결정 불가능한 것은 일반적인 정지 문제이지 — 어떤 특정한 M이나 어떤 특정한 w의 문제가 아니라 — 모든 ⟨M, w⟩에 답하는 일반 알고리즘이다.

7. 풍경 정리와 다음 강의

이번 강의에서 본 그림을 한 장으로 정리하자. 모든 언어의 우주 𝒫(Σ*) 안에는 다음과 같은 동심원이 있다.

가장 안쪽: 정규 언어 ⊊ 문맥 자유 언어 ⊊ 결정 가능 언어.
그 다음: 인식 가능 언어. 결정 가능 언어를 진정으로 포함한다(포함 사례: A_TM).
밖: 인식 불가능 언어. 결정 가능 + 인식 가능을 합쳐도 채울 수 없다(포함 사례: A_TM).
그리고 사실은, 정리 8.4가 말하듯 거의 모든 언어가 가장 바깥 동심원에 산다 — 알고리즘은 가산이지만 언어는 비가산이므로.

다음 강의에서는 환원 기법을 정식화한다. HALT_TM의 증명에서 본 비공식 환원을 매핑 환원으로 다듬고, 그 도구로 E_TM(공어 문제), EQ_TM(동치 문제), 그리고 — 충격적이게도 — 라이스의 정리(Rice's theorem)를 만나게 된다. 라이스 정리는 한 문장으로 요약된다: "튜링 기계가 인식하는 언어의 어떤 비자명한 성질도 결정 불가능이다." 결정 불가능의 풍경이 얼마나 광대한지를 보여주는 정리다.