강의 5

CF 펌핑 보조정리와 튜링 기계

스택 하나로는 닿지 않는 곳, 그리고 무한 테이프가 열어 주는 새 지평.

1. 스택 한 개의 한계를 어떻게 증명할까

정규 언어를 다룰 때 우리는 펌핑 보조정리(pumping lemma)로 한계선을 그었다. CFL에도 같은 정신의 도구가 있다. 다만 한 군데를 늘리는 정규판과 달리, 문맥 자유판은 두 군데를 동시에 부풀린다. 이유는 곧 드러난다. 충분히 긴 문자열의 파스 트리(parse tree)에는 같은 비단말이 어떤 경로 위에 두 번 등장할 수밖에 없기 때문이다.

보조정리 (CF 펌핑). L이 문맥 자유 언어이면 어떤 펌핑 길이 p ≥ 1이 존재해, 길이 |s| ≥ p인 모든 s ∈ L은 다음 분할

s = u v x y z

을 가진다.
  1. 모든 i ≥ 0에 대해 u vi x yi z ∈ L,
  2. |v y| > 0,
  3. |v x y| ≤ p.

조건 1은 v와 y를 같은 횟수만큼 동시에 늘리거나 줄여도 언어 안에 머무른다는 뜻. 조건 2는 적어도 한쪽은 비어 있지 않다는 뜻으로, "0번 펌프"가 무의미한 분할이 되는 것을 막는다. 조건 3은 v와 y가 서로 너무 멀리 떨어져 있지 못하도록 묶어 둔다.

한 줄 메모. v와 y는 같은 비단말의 두 등장 사이에서 자라난 부분이라, 자식과 손자, 손자의 손자 식으로 같은 규칙을 임의 횟수 끼워 넣을 수 있다. 그래서 둘이 함께 펌프된다.

2. 직관: 깊은 트리에는 같은 비단말이 두 번 나타난다

증명의 핵심 발상을 보자. 촘스키 정규형(Chomsky normal form)으로 옮긴 문법 G의 비단말 개수를 b개라 하고, 분기수가 최대 2인 이진 파스 트리를 생각하자. 깊이 h인 이진 트리의 잎 개수는 최대 2h이므로, 잎이 충분히 많으면 트리도 깊어야 한다. 길이 |s| ≥ 2b+1인 문자열의 파스 트리에는 길이 b+1을 넘는 어떤 뿌리-잎 경로가 존재하고, 그 경로 위에는 비둘기집 원리로 같은 비단말 R이 적어도 두 번 등장한다.

경로 위쪽의 R을 R위, 아래쪽의 R을 R아래라 하자. R아래가 만들어 내는 부분 문자열을 x, R위는 만들지만 R아래는 만들지 않는 양옆의 부분 문자열을 v와 y, R위 바깥의 좌우를 u와 z로 두면 s = u v x y z가 된다. 이제 R위의 자리에 R아래의 부분 트리를 끼워 넣거나(0회 펌프) R위의 부분 트리를 자기 자신 안에 거듭 끼워 넣어(i회 펌프) 새 파스 트리를 얻는다. 모두 G의 합법적 유도이므로 u vi x yi z ∈ L이다. 적절한 깊이에서 같은 비단말의 두 번째 등장을 처음 발견한다고 가정하면 |v x y|를 적당한 상수 p 이하로 묶을 수 있다.

펌핑 길이 p는 보통 2b+1 정도로 잡는다. 우리가 이 보조정리를 쓰는 데에 정확한 값은 거의 필요 없다 — 존재만 보장되면 충분하다.

3. 비-CFL 증명: { aⁿbⁿcⁿ : n ≥ 0 }

고전적인 비-CFL의 증인이다. CFG가 a와 b의 개수는 맞출 수 있어도, 거기에 더해 c의 개수까지 동시에 맞추는 것은 스택 하나로 감당이 안 된다는 직관을 펌핑 보조정리가 증명으로 굳혀 준다.

정리. L = { anbncn : n ≥ 0 } 은 문맥 자유 언어가 아니다.
증명 스케치. L이 CFL이라고 가정하고 모순을 끌어낸다. 펌핑 길이 p를 잡고 s = apbpcp를 고르자. |s| = 3p ≥ p이므로 보조정리가 적용된다. 어떤 분할 s = uvxyz가 세 조건을 모두 만족해야 한다.

조건 |vxy| ≤ p에 의해 vxy는 s 안에서 길이 p를 넘지 않는 한 토막을 차지한다. 따라서 vxy는 a-블록과 b-블록에 걸치거나, b-블록과 c-블록에 걸치거나, 한 블록 안에만 머무를 수밖에 없다. 어느 경우든 v, y에는 세 글자 a, b, c 가운데 적어도 한 종류는 들어 있지 않다.

이제 i = 2로 펌프해 본다. uv2xy2z를 보면 v와 y가 합쳐서 적어도 한 글자는 늘렸지만(조건 |vy| > 0), 누락된 그 글자의 개수는 그대로다. 그러면 a, b, c 셋의 개수가 어긋나며, 결과 문자열은 더 이상 akbkck 꼴이 아니다 — 즉 L에 속하지 않는다. 이는 보조정리 조건 1과 모순이다. 따라서 L은 CFL이 아니다.

같은 기법으로 { ww : w ∈ {0,1}* } 또한 비-CFL임이 보인다. 이쪽은 분할 자리를 따라가며 케이스 분석을 좀 더 신중하게 해야 한다.

4. 무한 테이프로 한 발 나아가다 — 튜링 기계

스택 한 개의 천장이 보였으니, 천장을 들어 올릴 차례다. 답은 의외로 단순하다. 읽기 전용 입력 테이프와 따로 떨어진 스택 대신, 읽고 쓰는 한 줄짜리 무한 테이프를 두자. 헤드(head)가 좌우로 자유로이 움직이며 어떤 칸이든 다시 들여다볼 수 있다. 이것이 1936년 앨런 튜링이 그린 그림이다.

정의 (튜링 기계). 튜링 기계 M은 7-튜플 ⟨Q, Σ, Γ, δ, q0, qaccept, qreject⟩이다.
  • Q: 유한 상태 집합, 단 qaccept와 qreject는 서로 다르다.
  • Σ: 입력 알파벳, 빈칸 기호 ␣ ∉ Σ.
  • Γ: 테이프 알파벳, Σ ⊆ Γ이고 ␣ ∈ Γ.
  • q0 ∈ Q: 시작 상태.
  • 전이 함수 δ : (Q ∖ {qaccept, qreject}) × Γ → Q × Γ × {L, R}.
δ(q, a) = (q′, b, D)는 "상태 q에서 헤드가 a를 보면, b를 덮어 쓰고 헤드를 D 방향(좌 L, 우 R)으로 한 칸 옮긴 뒤 q′로 간다"는 뜻이다.

테이프는 양쪽 또는 한쪽으로 무한히 뻗어 있다 — 어느 쪽으로 정의하든 표현력은 같다. 입력은 처음에 테이프의 왼쪽 끝부터 차례로 적혀 있고, 그 뒤로는 모두 빈칸 ␣이다. 헤드는 입력의 첫 칸을 본 채로 시작한다.

초기 테이프와 헤드:

   ⌊ 0 0 1 1 ␣ ␣ ␣ ␣ ⌋ ...
     ^
     헤드, 상태 q0

5. 구성, 계산, 그리고 세 가지 결말

한 시점에 TM이 무엇을 하는지 적어 두려면 세 정보가 필요하다. (i) 현재 상태, (ii) 테이프 내용, (iii) 헤드의 위치. 이 셋을 묶어 구성(configuration)이라 부르고, "상태 기호 직전에 끼워 넣은 한 줄"의 표기 u q v로 압축한다 — 헤드는 v의 첫 칸을 본다는 뜻이다.

한 구성에서 다음 구성으로 한 걸음 옮아가는 관계를 ⊢로 적는다. 시작 구성에서 출발해 ⊢로 이어지는 (유한 또는 무한) 열을 계산(computation)이라 한다. 계산의 결말은 정확히 셋이다.

정의 (인식 가능 vs 결정 가능). TM M이 받아들이는 문자열들의 집합 L(M) = { w : M이 w에서 qaccept로 멈춤 }을 M이 인식(recognize)하는 언어라 한다. 어떤 TM이 L을 인식하면 L은 튜링 인식 가능(Turing-recognizable, 또는 recursively enumerable)이다. 그 TM이 추가로 모든 입력에서 반드시 멈추면(거부도 분명히 거부로 멈추면) L은 결정 가능(decidable, recursive)하다.

차이는 단어 하나에 있다. "수락하지 않음"이 "거부로 멈춤"인지 아니면 "멈추지 않을 수도 있음"인지. 이 한 끗의 간격이 다음 강의들의 풍경을 거의 다 결정짓는다.

한 줄 메모. 결정 가능 ⊆ 인식 가능 임은 즉시 보이지만, 그 포함이 진부분집합임 — 즉 인식만 가능하고 결정은 불가능한 언어가 존재함 — 은 튜링이 정지 문제로 보였다. 이 강의에서 곧 만난다.

6. 첫 TM 예제: { 0n1n : n ≥ 0 } 결정하기

테이프와 좌우 이동의 위력을 가장 단순한 예에서 맛보자. 우리는 0과 1의 개수가 같은 언어 { 0n1n }이 결정 가능함을 직접 TM을 만들어 확인한다. (이 언어는 CFL이지만, 결정 가능하기도 하다.)

예제. 다음 알고리즘을 TM으로 구현한다.
  1. 왼쪽 끝의 첫 칸을 본다. 빈칸이면 입력은 ε이므로 수락하고 멈춘다.
  2. 0이면 그 칸을 표식 X로 덮어 쓰고 오른쪽으로 이동, 가장 오른쪽의 1을 찾아 표식 Y로 덮어 쓴다. 1을 찾기 전에 빈칸이나 다른 X를 만나면 거부.
  3. 다시 왼쪽 끝까지 돌아온다.
  4. 2-3을 반복하다가, 1단계에서 첫 칸이 0이 아니면 다음을 검사한다. 남은 글자가 모두 X와 Y뿐이고 1이나 0이 더 없으면 수락, 그렇지 않으면 거부.
한 발짝의 진행을 그려 보자. 
시작:        ⌊ 0 0 1 1 ␣ ⌋   상태 q0, 헤드는 첫 0
1회 한 쌍:  ⌊ X 0 1 Y ␣ ⌋   상태 q왼쪽, 헤드는 X
2회 한 쌍:  ⌊ X X Y Y ␣ ⌋   상태 q점검, 헤드는 첫 X
점검 통과:  ⌊ X X Y Y ␣ ⌋   상태 qaccept → 수락
모든 입력에서 위 절차는 유한 단계 안에 멈춘다 — 한 번 순회할 때마다 0과 1 한 쌍이 X와 Y로 표시되어 작업 대상이 줄어들기 때문이다. 따라서 이 TM은 { 0n1n }을 결정한다.

좀 더 야심 찬 예로 { wcw : w ∈ {0,1}* }를 들 수 있다. 이쪽은 c 양쪽의 두 부분이 글자별로 같은지 비교해야 한다. 한 글자씩 표식을 남기며 좌우를 오가는 동작은 TM의 자유로운 헤드 움직임이 없으면 흉내 내지 못한다 — 어떤 PDA로도 결정할 수 없는 언어다.

7. 다음 풍경 — Church-Turing 명제

튜링 기계의 정의는 미니멀하다. 그러나 다중 테이프, 비결정성, 이차원 테이프, 무작위 접근 같은 어떤 변종을 가져다 붙여도 결정 가능한 언어 부류는 변하지 않는다. 더 놀라운 사실은 람다 대수, μ-재귀 함수, 마르코프 알고리즘 등 전혀 다른 출발점에서 시작된 계산 모형들이 모두 같은 언어 부류를 결정한다는 것이다. 이 합치를 한 문장으로 요약한 것이 Church-Turing 명제다 — 직관적으로 "알고리즘으로 풀 수 있는 문제"란 정확히 튜링 기계가 결정할 수 있는 문제이다.

다음 강의부터는 이 무한 테이프 기계 위에서 결정 가능한 문제들을 사냥하고, 결정 불가능한 영역의 첫 표본 — 정지 문제 — 을 향해 다가간다. 펌핑 보조정리가 우리에게 "할 수 없음"의 첫 맛을 보여 주었다면, 다음에 만날 대각화는 그 맛을 한층 깊이 다듬어 줄 것이다.