강의 10

계산 이력 방법 — 시간을 문자열로 펼치기

LBA, CFG, 그리고 도미노가 모두 같은 함정에 빠지는 이유

1. 시간을 문자열로 묶다

지난 강의의 환원들은 대체로 "M이 무언가 수락하면 ~을 한다" 식의 한 줄 트릭으로 끝났다. 그러나 우리가 결정 불가능성을 더 작고 더 약한 계산 모델로 — 예를 들어 선형 유계 오토마타(LBA)나 문맥 자유 문법(CFG)으로 — 가져가려 할 때, 그런 트릭만으로는 부족하다. 이 모델들은 임의의 튜링 기계를 시뮬레이션할 만큼 똑똑하지 않기 때문이다.

해법은 의외다. 우리는 시간을 문자열로 펼친다. TM의 계산 한 번 — 시작에서 끝까지 — 을 통째로 하나의 문자열로 적어두면, 그 문자열을 검사하는 일은 훨씬 단순한 모델로도 가능해진다. 이 기법을 계산 이력 방법(computation history method)이라 부른다. 시간이 약점이라면 시간을 공간으로 환산해버리자는 것이다.

정의 10.1 (구성과 계산 이력). TM M의 구성(configuration)은 어떤 순간의 테이프 내용, 헤드 위치, 현재 상태를 나타내는 문자열이다. 흔히 uqv 형식으로 적는데, 여기서 q는 상태이고 헤드는 v의 첫 글자 위에 있다.

입력 w에 대한 M의 수락 계산 이력(accepting computation history)은 다음 조건을 만족하는 구성들의 시퀀스

C₀, C₁, ..., C_k

이다.

C₀은 입력 w에 대한 시작 구성이다.
각 i에 대해 C_i ⊢ C_i+1 (C_i가 한 단계 만에 C_i+1로 옮겨갈 수 있다).
C_k는 수락 구성이다.

거부 계산 이력은 C_k가 거부 구성인 경우이다.

핵심 관찰은 이렇다. M이 w를 수락하는가 묻는 것은 곧 "C₀에서 시작해 한 단계씩 합법적으로 옮겨가며 수락 구성에 도달하는 시퀀스가 존재하는가"를 묻는 것과 같다. 그리고 "한 단계 합법성"은 굉장히 국소적인 검사이다 — C_i와 C_i+1이 헤드 주변 두세 글자만 다르고 나머지는 동일하면 된다. 국소성은 약한 모델이 다룰 수 있는 친구이다.

2. 선형 유계 오토마타

정의 10.2 (LBA). 선형 유계 오토마타(linear bounded automaton)는 입력 길이만큼의 테이프 칸만 사용하는 튜링 기계이다. 더 정확히, 입력 양 끝에 마커가 있어 헤드가 그 바깥으로 나갈 수 없다.

LBA는 강력하다 — 모든 문맥 의존 언어를 인식한다. 그러나 동시에 약한 면도 있다. 사용 가능한 공간이 입력으로 제한되므로, 가능한 구성의 수가 유한하다. 이 유한성이 모든 차이를 만든다.

보조정리 10.3. 상태 집합 Q, 테이프 알파벳 Γ, 입력 길이 n인 LBA의 가능한 구성 수는 |Q| · n · |Γ|ⁿ개로 유한하다.

증명 스케치. 구성은 (상태, 헤드 위치, 테이프 내용)의 삼중쌍이다. 상태는 |Q|가지, 헤드 위치는 n가지(왼쪽 끝부터 오른쪽 끝까지), 테이프 내용은 각 칸이 |Γ| 중 하나이므로 |Γ|ⁿ가지이다. 곱하면 위의 식이 나온다. ∎

정리 10.4. A_LBA = { ⟨M, w⟩ : M은 LBA, M이 w를 수락 }은 결정 가능하다.

증명. 결정자 D는 다음과 같이 동작한다. 입력 ⟨M, w⟩에 대해 |Q| · n · |Γ|ⁿ단계까지 M을 시뮬레이션한다. 만약 그 안에 수락하면 수락. 만약 그 안에 거부하거나 같은 구성이 두 번 나타나면 거부. 시뮬레이션이 위의 한계를 넘어가면 — 비둘기집 원리에 의해 — M은 어딘가에서 같은 구성을 두 번 거쳤을 것이다. 즉 LBA는 무한 루프에 갇혔다. 따라서 거부한다. ∎

여기까지는 LBA가 다른 어떤 TM 종류보다도 다루기 쉽다는 좋은 소식이다. 그러나 LBA의 보다 풍부한 질문은 — 마치 TM에서처럼 — 곧장 결정 불가능 영역으로 들어간다.

3. E_LBA — LBA가 빈 언어를 인식하는가

정의 10.5. E_LBA = { ⟨M⟩ : M은 LBA이고 L(M) = ∅ }.

정리 10.6. E_LBA는 결정 불가능하다.

증명 (A_TM ≤_m E_LBA). 핵심 아이디어 — LBA가 일반 TM의 계산 이력을 검사하도록 만든다. 임의의 ⟨M, w⟩가 주어졌을 때 LBA B를 다음과 같이 구성한다.

B의 입력 형식: 후보 시퀀스 #C₀#C₁#...#C_k#.

B는 다음을 차례로 검사한다.

C₀이 M의 w 시작 구성과 일치하는가?
각 인접 쌍 (C_i, C_i+1)이 한 단계 합법적인 천이인가?
C_k가 M의 수락 구성인가?

이 모든 검사는 입력 길이 안에서 충분히 수행된다 — B는 입력 위를 좌우로 이동하며 # 사이의 두 구성을 비교하기만 하면 된다. 그러므로 B는 진짜로 LBA이다.

이제 정확히 다음이 성립한다.

L(B) ≠ ∅ ⇔ M의 w에 대한 수락 계산 이력이 존재 ⇔ M이 w를 수락 ⇔ ⟨M, w⟩ ∈ A_TM.

대우로, ⟨M, w⟩ ∉ A_TM ⇔ ⟨B⟩ ∈ E_LBA이다. 환원 함수 f(⟨M, w⟩) = ⟨B⟩는 계산 가능하다. 따라서 코A_TM ≤_m E_LBA이고 E_LBA는 결정 불가능하다. ∎

이 환원의 묘미는 약한 모델(LBA)에 강한 모델(임의의 TM)의 모든 행동을 텍스트로 압축해 떠넘긴다는 점이다. LBA는 시뮬레이션할 수 없지만 검산은 할 수 있다. 검산이라는 가벼운 일조차 결정 불가능을 부른다.

4. ALL_CFG — CFG가 모든 문자열을 생성하는가

이번에는 도구를 한 단계 더 약화시킨다 — 문맥 자유 문법으로.

정의 10.7. ALL_CFG = { ⟨G⟩ : G는 CFG이고 L(G) = Σ* }.

정리 10.8. ALL_CFG는 결정 불가능하다.

증명의 핵심은 영리한 뒤집기이다. CFG는 일반적으로 "잘못된 계산 이력"의 집합 — 합법적이지 않은 시퀀스의 모임 — 을 표현할 수 있다. 그러면 "잘못된 이력의 집합이 Σ* 전부인가"라는 질문은 "올바른 이력이 단 하나도 없는가"와 같고, 이는 곧 "M이 w를 거부하는가"이다.

증명 스케치 (A_TM ≤_m 코ALL_CFG). 입력 ⟨M, w⟩에 대해 다음 언어를 생성하는 CFG G를 만든다.

L(G) = { x ∈ Σ* : x는 M의 w에 대한 수락 계산 이력이 아니다 }.

이렇게 잡으면 L(G) = Σ* ⇔ 수락 이력이 하나도 없음 ⇔ M이 w를 수락하지 않음이 된다.

왜 "올바르지 않다"는 CFG로 표현 가능한가? 후보 문자열이 #C₀#C₁#...#C_k# 모양이라 가정하면, 그것이 수락 이력이 아닐 조건은 다음 중 적어도 하나이다.

(A) 모양 자체가 틀렸다 (#로 구분된 블록이 아니다).
(B) C₀이 시작 구성이 아니다.
(C) 어떤 i에서 C_i가 C_i+1로 합법적으로 옮겨가지 못한다.
(D) C_k가 수락 구성이 아니다.

(A), (B), (D)는 정규 언어에 가깝고 — 따라서 CFG로 — 표현 가능하다. 진짜 트릭은 (C)이다. CFG는 본래 "C_i와 C_i+1가 다르다"고 직접 말하기 어렵다. 푸시다운 자동기는 한 번에 두 개의 구성을 동시에 비교할 수 없기 때문이다.

홀짝 구성 뒤집기 트릭. 우리는 계산 이력의 형식을 살짝 비튼다 — 짝수 번째 구성은 그대로 적고, 홀수 번째 구성은 역순으로 적는다. 즉 #C₀#C₁^R#C₂#C₃^R#... 와 같이. 이렇게 하면 인접한 두 구성 C_i와 C_i+1^R이 서로 마주보고 거울처럼 적힌다. 이 거울 형식은 푸시다운 스택으로 처리할 수 있다 — C_i를 푸시한 뒤 C_i+1^R를 비교하면서 팝하면 된다. 비교 도중 단 한 곳이라도 한 단계 천이 규칙에 어긋나는 차이를 발견하면 그 후보는 (C)에 의해 "수락 이력이 아니다"로 분류된다.

이 G를 잘 설계하면 정확히 "올바르지 않은 이력들"을 받는다. M이 w를 수락하지 않으면 어떤 후보도 수락 이력일 수 없으므로 L(G) = Σ*. M이 수락하면 그 단 하나의 진짜 수락 이력은 G가 받지 않으므로 L(G) ≠ Σ*. 따라서 ⟨M, w⟩ ∈ 코A_TM ⇔ ⟨G⟩ ∈ ALL_CFG이고, ALL_CFG는 결정 불가능하다. ∎

왜 뒤집어야 하는가. CFG로 ww 같은 언어 — "두 번 똑같이 적은 문자열" — 는 만들 수 없지만, ww^R — "두 번째 절반을 거꾸로 적은 회문 모양" — 은 매우 자연스럽게 만들 수 있다. 계산 이력의 인접 구성을 비교하려면 똑같은 형태가 필요한데, 마침 푸시다운 스택은 회문을 좋아한다. 이 우연이야말로 환원이 통하는 비밀이다.

5. Post 대응 문제(PCP)

마지막으로, 계산과는 전혀 관련 없어 보이는 — 도미노 퍼즐의 — 문제를 본다.

정의 10.9 (PCP). 도미노 모음을 다음과 같이 적자.

P = { [t₁/b₁], [t₂/b₂], ..., [t_n/b_n] }

각 도미노는 윗변 t_i와 아랫변 b_i가 적힌 카드이다. 대응(match)이란 (중복 사용 허용) 도미노들의 시퀀스 [t_i₁/b_i₁], ..., [t_{i_k}/b_{i_k}]로서

t_i₁ t_i₂ ... t_{i_k} = b_i₁ b_i₂ ... b_{i_k}

가 성립하는 것을 말한다. PCP = { ⟨P⟩ : P는 대응을 갖는다 }.

작은 예제. P = { [b/ca], [a/ab], [ca/a], [abc/c] }. 시퀀스 [a/ab], [b/ca], [ca/a], [a/ab], [abc/c]를 차례로 놓으면 윗줄과 아랫줄이 모두 abcaaabc로 일치한다. 이런 대응을 손으로 찾아본 학생이라면 — 일반적인 PCP가 얼마나 어려운지 직감했을 것이다.

정리 10.10 (Post, 1946). PCP는 결정 불가능하다.

증명 직관 (A_TM ≤_m PCP). 임의의 ⟨M, w⟩가 주어졌을 때, 그 수락 계산 이력에 정확히 대응하는 도미노 시스템 P를 설계한다. 도미노들은 다음 역할을 갖도록 정한다.

시작 도미노: 윗줄에 "#"만, 아랫줄에 "#C₀#"를 적어, 아랫줄이 먼저 한 구성만큼 앞서 나가게 한다.
천이 도미노들: 각 가능한 한 단계 천이 (헤드 주변의 짧은 변환)에 대해, 윗줄에 "이전" 부분, 아랫줄에 "이후" 부분을 적은 도미노를 둔다.
복사 도미노: 헤드에서 멀리 떨어진 위치는 그대로 유지된다. 각 테이프 글자 a에 대해 윗·아랫줄 모두 a인 도미노를 둔다.
마무리 도미노: 수락 상태에 도달했을 때 윗줄을 따라잡게 만드는 청소(cleanup) 도미노들.

대응을 만들려고 시도하는 일은 곧 M의 계산을 한 단계씩 그려나가는 일이 된다 — 도미노들이 서로 맞물리도록 강제하는 유일한 방법은 합법적인 다음 구성을 적어 가는 것이다. 따라서 P가 대응을 가짐 ⇔ M의 수락 이력 존재 ⇔ M이 w를 수락이 된다. (이 환원의 정확한 디테일 — 시작과 끝의 처리, 정확한 도미노 수 — 는 한 페이지가 넘는 사례 분석이지만, 본질은 위와 같다.) ∎

PCP는 1946년에 정의되었지만 결정 불가능성 증명은 1950년대에 와서야 완성되었다. 도미노 퍼즐이라는 어린이 게임이 튜링 기계만큼이나 강력하다는 사실은 — 학문 전반에 걸쳐 — 환원의 위력을 증언하는 가장 인상 깊은 사례 중 하나이다.

6. 마무리

계산 이력은 시간이라는 추상을 문자열이라는 구체로 끌어내리는 망원경이다. 이 망원경 하나로 우리는 LBA의 빈 언어, CFG의 만물 언어, 그리고 도미노 퍼즐까지 결정 불가능 영역으로 끌어들였다. 다음 강의에서는 정반대 방향의 마법을 본다 — 자기 자신을 출력하는 프로그램, 그리고 그로부터 나오는 우아한 회귀 정리이다.