강의 6

튜링 기계의 변형들과 처치-튜링 명제

테이프를 늘리고, 갈래를 치고, 결과만 토해내도 — 결국 우리는 같은 산에 오른다.

1. 변형이라는 유혹

지난 강의에서 정의한 단일 테이프 결정적 튜링 기계(deterministic Turing machine, DTM)는 분명 강력하지만, 그 위에서 알고리즘을 직접 짜본 사람이라면 누구나 한 번쯤은 이렇게 외친다: "테이프 하나로는 못 해 먹겠다." 입력은 그대로 두고 작업 공간은 따로 쓰고 싶고, 결과는 또 다른 곳에 적고 싶다. 갈래마다 다른 추측을 시도해보고 싶고, 때로는 입력을 받지 않고 그냥 모든 출력을 토해내는 기계가 더 자연스럽기도 하다.

이 강의의 결론은 한 문장으로 요약된다: 이 모든 변형은 표준 단일 테이프 TM과 동치이다. 표현력은 같지만 사고의 편의는 천양지차이므로, 우리는 앞으로 증명에서 가장 편한 모델을 골라 쓸 권리를 얻는다. 그리고 이 권리의 철학적 일반화가 바로 처치-튜링 명제(Church-Turing thesis)이다.

2. 다중 테이프 튜링 기계

정의 6.1 (다중 테이프 TM). k-테이프 튜링 기계는 k개의 양방향 무한 테이프와 각각 독립적으로 움직이는 k개의 헤드를 갖는다. 입력은 1번 테이프에 쓰여 있고 나머지 테이프는 빈 칸(␣)으로 시작한다. 전이 함수는

δ : Q × Γ^k → Q × Γ^k × {L, R, S}^k

이며, 한 단계에서 k개의 헤드 아래 기호를 동시에 읽고, k개의 기호를 쓰고, 각 헤드를 독립적으로 좌(L)·우(R)·정지(S) 중 하나로 움직인다.

S(정지) 옵션이 등장했다고 당황할 필요는 없다. 우리는 곧 이 모델을 단일 테이프 모델로 시뮬레이션하면서 어차피 표현력이 같음을 보일 것이고, 실제로 단일 테이프 모델에서도 두 단계로 쪼개면 정지를 흉내 낼 수 있다.

정리 6.2. 모든 다중 테이프 TM은 어떤 단일 테이프 TM과 동치이다. 즉, 같은 언어를 인식한다.

증명 스케치. k-테이프 TM M이 주어졌을 때, 단일 테이프 TM S는 한 줄에 모든 정보를 압축한다. 핵심 아이디어는 두 가지다.

트랙 인터리빙. S는 k개의 테이프 내용을 구분 기호 #로 잘라 한 줄에 늘어놓는다. 입력이 w₁w₂…w_n이라면 초기 테이프는
#w₁w₂…w_n#␣#␣#…#
형태가 된다. 각 # 사이의 구간이 M의 한 테이프에 대응한다.
헤드 위치 마커. M의 각 헤드 위치를 표시하기 위해 알파벳을 두 배로 늘려 "점이 찍힌" 버전 Γ̇를 도입한다. i번째 구간에서 단 하나의 칸에만 점을 찍어 헤드의 위치를 기록한다.

S는 M의 한 단계를 다음과 같이 흉내 낸다. 먼저 테이프를 처음부터 끝까지 한 번 훑어 k개의 점 찍힌 기호를 메모리(즉, 상태)에 기록한다. δ를 적용해 새 기호와 이동 방향을 결정한다. 다시 테이프를 훑으며 k개 위치에 새 기호를 쓰고 점을 옆 칸으로 옮긴다. 만약 어떤 점이 자신의 # 경계에 부딪히면, 그 구간 오른쪽 전체를 한 칸씩 밀어 새 빈 칸을 삽입한다 — 이것이 양방향 무한 테이프를 단일 테이프 위에서 흉내 내는 비용이다.

M이 t(n)단계 동안 사용하는 공간은 O(t(n))이므로, S의 한 단계는 O(t(n))시간이 걸리고 전체적으로 O(t(n)²)시간이면 충분하다. 시간 복잡도는 제곱으로 늘지만, 인식되는 언어 자체는 한 글자도 바뀌지 않는다.

한 줄 메모. "여러 테이프 = 빠른 단일 테이프"이다. 알고리즘 설계 시에는 다중 테이프로 사고하고, 이론 증명 시에는 단일 테이프로 환원하는 것이 표준 워크플로우다.

3. 비결정적 튜링 기계

정의 6.3 (NTM). 비결정적 튜링 기계(nondeterministic TM, NTM)는 전이 함수가

δ : Q × Γ → 𝒫(Q × Γ × {L, R})

인 점만 다르다. 한 구성에서 가능한 다음 구성이 여럿일 수 있고, NTM N은 적어도 하나의 계산 분기가 수락 상태에 도달하면 입력을 수락한다. NTM의 계산은 트리이다 — 뿌리는 시작 구성이고 각 노드의 자식은 그 구성에서 가능한 다음 구성들이다.

정리 6.4. 모든 NTM은 어떤 결정적 TM과 동치이다.

증명 스케치. NTM N이 주어지면 3-테이프 결정적 TM D를 만든다. 1번 테이프는 입력을 그대로 보존하고, 2번 테이프는 현재 시뮬레이션 중인 분기의 작업 공간이며, 3번 테이프는 분기 주소(address)를 담는다.

각 분기 주소는 어떤 정수의 수열 b₁b₂…b_m로, "1단계에서 b₁번째 선택지, 2단계에서 b₂번째 선택지, …"라는 의미다. D는 다음을 반복한다.

3번 테이프에 적힌 주소를 따라 N을 시뮬레이션한다. 도중에 주소가 가리키는 선택지가 존재하지 않으면(δ가 그만큼의 갈래를 갖지 않음) 이 분기를 포기하고 다음 주소로 넘어간다.
그 분기가 수락 구성에 도달하면 D도 수락한다.
그렇지 않으면 3번 테이프의 주소를 사전식 다음(lexicographically next) 문자열로 갱신한다.

이것은 본질적으로 계산 트리에 대한 너비 우선 탐색(breadth-first search, BFS)이다. 깊이 우선 탐색(DFS)은 왜 안 되는가? 어떤 분기가 무한 루프에 빠지면 영영 돌아오지 못해, 옆 가지에 있을지 모를 수락 분기를 발견하지 못하기 때문이다. BFS는 모든 깊이 d의 노드를 깊이 d+1로 넘어가기 전에 다 방문하므로, 수락 분기가 어딘가에 있다면 유한 시간 안에 반드시 만난다.

마지막으로 정리 6.2를 적용하면 3-테이프 결정적 TM은 단일 테이프 결정적 TM으로 환원된다. 결국 NTM ≡ DTM.

한 줄 메모. 시간으로 환산하면 결정적 시뮬레이션은 분기 수에 대해 지수적으로 비용을 치른다. P vs NP의 진앙지는 바로 여기다.

4. 열거기와 인식 가능성의 또 다른 얼굴

정의 6.5 (열거기). 열거기(enumerator) E는 입력 없이 작동하는 튜링 기계 변형으로, 작업 테이프와 별개의 출력 테이프를 가진다. E는 작동 도중 임의의 시점에 출력 테이프에 쓴 문자열을 특수 표시 #로 끝내며 "출력했다"고 선언한다. E가 열거하는 언어는 E가 언젠가 출력하는 모든 문자열의 집합이다(중복은 허용되며, 순서도 임의다).

정리 6.6. 언어 A가 튜링 인식 가능(Turing-recognizable)인 것과 A가 어떤 열거기에 의해 열거되는 것은 동치이다.

증명 스케치.

(⇐) E가 A를 열거한다고 하자. TM M은 입력 w에 대해 E를 시뮬레이션하면서 E가 새 문자열을 출력할 때마다 그것을 w와 비교한다. 같으면 수락하고, 아니면 계속 시뮬레이션한다. w ∈ A면 언젠가 E가 w를 출력하므로 M은 수락한다. w ∉ A면 M은 영원히 멈추지 않는다 — 인식의 정의에 부합한다.

(⇒) TM M이 A를 인식한다고 하자. 입력 알파벳을 사전식으로 정렬해 s₁, s₂, … 로 두고, 열거기 E는 다음과 같이 동작한다.

i = 1, 2, 3, … 에 대해, M을 s₁, …, s_i 각각에 대해 i단계까지 시뮬레이션한다. 그동안 i단계 안에 수락하는 입력이 있으면 출력한다.

이른바 대각선식 시간 분배(dovetailing)다. M이 w를 k단계에 수락한다면, i ≥ max(k, |w|+1)인 모든 라운드에서 w가 출력된다. 따라서 E는 정확히 A를 열거한다. 단순히 "s₁에 대해 M을 끝까지 돌리고, 다음에 s₂로…"라는 순진한 방법은 M이 첫 입력에서 멈추지 않으면 영원히 갇히기 때문에 통하지 않는다.

예제 6.7. 모든 짝수 길이 이진 회문(palindrome)의 집합을 인식하는 TM은 쉽게 만들 수 있다. 같은 집합을 열거하는 열거기도 쉽다 — 길이순으로 모든 이진 문자열을 생성하면서 회문인 것만 출력한다. 두 모델 사이의 환원이 무엇처럼 느껴지는지 직관을 갖자.

5. 처치-튜링 명제

지금까지 살펴본 변형은 빙산의 일각이다. 사람들은 "현실적인 계산 모델"이라 부를 만한 거의 모든 것을 정의해보았다.

람다 계산(λ-calculus). 알론조 처치(Alonzo Church)가 1930년대에 정의한, 순수 함수 추상화와 적용만으로 이루어진 형식 체계. 모든 계산을 함수 (λx.x) 같은 항으로 표현한다.
회귀 함수(recursive functions). 괴델-에르브랑-클레네의 부분 회귀 함수 클래스. 0, 후행자, 사영, 합성, 원시 회귀, 최소화 연산자(μ-operator)로 닫힌 함수들의 모임.
무제한 레지스터 머신(unlimited register machine, URM). 자연수 레지스터 무한 개와 증가·감소·점프 명령으로 동작하는 추상 컴퓨터. 셰퍼드슨-스터지스가 정리한 모델이다.
마르코프 알고리즘, 태그 시스템, 회로 패밀리, 세포 자동자(cellular automaton) 등.

놀랍게도 이 모든 모델은 정확히 같은 함수 클래스 — 부분 회귀 함수, 곧 튜링 계산 가능 함수 — 를 정의한다. 1936년 처치와 튜링은 이 사실을 다음 명제로 결정화했다.

처치-튜링 명제. "직관적 의미에서 알고리즘으로 계산 가능한 함수"의 클래스는 정확히 튜링 기계가 계산하는 부분 함수의 클래스와 같다.

이것은 정리가 아니다. 좌변의 "직관적"이라는 말 때문에 수학적으로 증명할 대상이 아니라, 직관적 개념과 형식적 개념을 동일시하자는 명제이자 약속이다. 그러나 90년이 지난 지금도 어떤 반례도 발견되지 않았고, 위에서 본 다양한 모델들의 등가성이 강력한 경험적 증거를 제공한다. 우리는 이제 "어떤 알고리즘이 존재한다"는 진술을 "어떤 튜링 기계가 존재한다"로 자유로이 바꿔 쓸 수 있는 면허를 갖게 된다.

한 줄 메모. 양자 컴퓨터도 처치-튜링 명제를 깨지 않는다. 양자 회로는 — 비효율적이긴 해도 — 고전 TM으로 시뮬레이션 가능하다. 무엇이 깨질지 모를 후보는 "효율적" 처치-튜링 명제(다항식 시간 버전), 곧 강처치-튜링 명제뿐이다.

6. 모델은 옷이고 알고리즘은 사람이다

강의를 마치며 한 가지만 기억하자. 단일 테이프든, 다중 테이프든, 비결정적이든, 람다 항이든, 우리가 "이것은 알고리즘이다"라고 부를 수 있는 것은 어떤 모델에서 표현해도 같은 함수를 계산한다. 모델은 알고리즘에 입히는 옷이다. 옷이 다양해도 사람은 한 명이다.

이것이 이론적으로 의미하는 바는 분명하다. 다음 강의부터 우리는 "결정 가능"과 "결정 불가능"을 자유롭게 말할 것인데, 이 개념들은 어떤 모델을 골라도 변하지 않는다. 다음 강의에서는 이 자유를 활용해 정규 언어와 문맥 자유 언어에 대한 수많은 결정 문제를 — 의외로 평이하게 — 알고리즘으로 풀어낼 것이다. 이후 강의 8에서 비로소 결정 불가능의 첫 풍경을 만나게 된다.