QUINE에서 괴델까지, 자기 참조의 한 줄 마법
다음과 같은 작은 도전이 있다. 입력 없이 실행했을 때 자기 자신의 소스 코드를 그대로 출력하는 프로그램을 작성하라. "그냥 파일을 읽으면 되지 않나?" 하는 학생도 있을 것이다. 그러나 그건 반칙이다 — 외부 자원에 접근하지 말고, 코드 자체의 글자만으로 그 코드 전체를 재구성해야 한다. 이런 프로그램을 콰인(quine)이라 부른다.
처음 시도하면 곧 무한 회귀에 빠진다. 코드를 출력하려면 그 코드를 어딘가에 적어둬야 하는데, 그 적어둔 부분도 출력해야 하므로 또 적어두고 — 마치 거울 두 개를 마주 보게 한 듯하다. 그러나 콰인은 가능하다. 그리고 콰인의 일반화가 바로 회귀 정리(recursion theorem)이다. 회귀 정리는 단지 호기심 차원의 트릭이 아니라, 임의의 튜링 기계가 "자기 자신의 기술(description)에 접근할 수 있다"는 강력한 결론을 보장한다.
"자기 자신의 코드에 접근한다" — 이 말은 신비롭게 들리지만, 회귀 정리가 보장하는 바는 매우 실용적이다. M이 자신의 ⟨M⟩을 마치 입력처럼 갖다 쓰는 것을 우리가 합법화한다는 뜻이다. 이 권한이 있으면 결정 불가능성, 의미적 성질의 한계, 심지어 괴델의 불완전성까지 한 줄 증명이 가능해진다.
회귀 정리의 핵심은 두 단계 구성이다. 우리는 먼저 "어떤 고정된 문자열 t를 출력하는 기계"를 만드는 일반적인 절차가 존재함을 본다. 그런 다음 이 절차를 자기 자신에게 적용하여 콰인을 얻는다.
보조정리 11.1 (출력 기계 생성). 임의의 문자열 t에 대해, 입력에 무관하게 t를 출력하고 정지하는 TM ⟨Pt⟩의 기술을 만드는 계산 가능 함수 q : t ↦ ⟨Pt⟩가 존재한다.
이는 직관적으로 자명하다. q는 단순히 "t를 테이프에 쓰고 정지"라는 코드를 t의 글자 수에 맞게 펼쳐 적기만 하면 된다. q 자체도 짧은 알고리즘이다.
정리 11.2 (SELF, 자기 출력 TM의 존재). 입력에 무관하게 자기 자신의 기술 ⟨SELF⟩를 출력하고 정지하는 튜링 기계 SELF가 존재한다.
증명. SELF를 두 부분 A와 B의 직렬 결합으로 구성한다. SELF = AB.
B의 역할. B는 테이프에 이미 어떤 문자열 t가 적혀 있다고 가정한다. B는 다음을 수행한다.
즉 B의 입력 t에 대한 출력은 ⟨Pt⟩t이다.
A의 역할. A는 입력을 무시하고 어떤 고정된 문자열을 테이프에 쓰고 B에게 넘겨주는 — q(⟨B⟩)에 해당하는 — 기계이다. 즉 A는 ⟨B⟩를 테이프에 출력하는 P⟨B⟩이다. 그러므로 A의 기술 ⟨A⟩는 정확히 q(⟨B⟩)이다.
전체 동작. SELF = AB가 실행되면 다음이 차례로 일어난다.
따라서 SELF의 최종 출력은 ⟨A⟩⟨B⟩ = ⟨AB⟩ = ⟨SELF⟩이다. SELF는 자기 자신의 기술을 출력한다. ∎
이 두 단계 구성은 이론과 실제 양쪽에서 우아하다. A는 "B를 테이프에 적는다"는 단 한 가지 일을 하고, B는 "지금 적힌 것이 곧 무엇을 출력해야 할지를 말해주는 명세"라고 간주하여 그 명세에 따라 자기 자신을 출력한다. 콰인 작성 대회의 우승작들은 모두 이 패턴의 변주이다.
정리 11.3 (Kleene의 회귀 정리, 약식 진술). T를 입력 (x, w)를 받는 임의의 TM이라 하자. 그러면 다음을 만족하는 TM R이 존재한다.
R(w) = T(⟨R⟩, w) (모든 w에 대하여)
다시 말해, R은 자기 자신의 기술 ⟨R⟩에 자유롭게 접근하면서 — 마치 그것이 추가 입력으로 주어진 것처럼 — 임의의 계산 T를 수행할 수 있다.
증명 스케치. 보조정리 11.2의 SELF 구성을 일반화한다. R을 세 부분 A'B'T의 결합으로 만든다. A'B'는 SELF와 똑같은 두 단계 구성을 약간 확장하여 — 입력 w를 보존하면서 — 자기 자신의 기술 ⟨R⟩을 테이프에 추가로 마련한다. 그런 뒤 T를 (⟨R⟩, w) 위에서 호출한다. 결국 R(w) = T(⟨R⟩, w)이다. ∎
회귀 정리의 미덕은 "괜히 만들어진 자기 참조" 같은 인상에도 불구하고 어디에서나 등장한다는 점이다. 이제 그 위력을 두 가지 응용으로 본다.
대각선 논법으로 ATM의 결정 불가능성을 보였던 기억이 있을 것이다. 이제 회귀 정리를 활용하면 같은 결과를 한층 직접적이고 짧게 얻을 수 있다.
정리 11.4. ATM은 결정 불가능하다.
증명 (회귀 정리 사용). 모순을 위해 ATM의 결정자 H가 존재한다고 가정하자. 회귀 정리에 의해, 자기 자신의 기술 ⟨D⟩에 접근 가능한 TM D를 다음과 같이 정의할 수 있다.
D = "입력 w에 대해 — H(⟨D⟩, w)를 실행한다. H가 수락하면 D는 거부, H가 거부하면 D는 수락한다."
이제 D를 자기 자신의 기술 ⟨D⟩ 위에서 실행한 결과를 따져보자.
이는 명백한 모순이다. 따라서 H는 존재하지 않는다. ∎
대각선 논법과 회귀 정리는 사실상 같은 동전의 양면이다. 대각선 논법이 "한 줄에 하나씩 위배되는 입력을 만든다"는 표 만들기 작업이라면, 회귀 정리는 "그 위배를 한 점에 압축한 자기 참조"이다. 둘은 동치이다.
회귀 정리는 결정 불가능성보다 한 단계 더 강한 결론도 즉시 준다. "최소 길이 TM"의 집합을 보자.
정의 11.5. ⟨M⟩이 최소(minimal)이라는 것은, L(M) = L(M')이고 |⟨M'⟩| < |⟨M⟩|인 다른 TM M'이 존재하지 않음을 의미한다. MINTM = { ⟨M⟩ : ⟨M⟩은 최소 }.
정리 11.6. MINTM은 튜링 인식 불가능하다.
증명 스케치. 모순을 위해 MINTM를 인식하는 열거자(enumerator) E가 존재한다고 가정하자. E는 MINTM의 원소를 차례로 출력한다(인식 가능 = 열거 가능). 이제 회귀 정리로 다음 TM C를 만든다.
C = "입력 w에 대해 — 자기 자신의 기술 ⟨C⟩를 얻는다. E를 가동하여 |⟨C⟩|보다 긴 기술 ⟨D⟩가 처음 출력될 때까지 기다린다. 그러면 D를 w 위에서 시뮬레이션하고 그 결과를 따라간다."
그런데 이렇게 만든 C에 대해 다음이 성립한다.
그런데 D는 E가 출력한 — 즉 최소라고 인증된 — 기계이다. 그런 D보다 더 짧은 C가 같은 언어를 인식한다는 것은 D가 최소라는 사실과 모순이다. 따라서 E는 존재하지 않는다. ∎
이 증명에서 회귀 정리가 한 일은 단 하나 — C가 자기 자신의 길이를 알 수 있게 해준 것이다. "내가 얼마나 긴지 모르는 기계"는 "나보다 긴 것을 기다리겠다"고 말할 수 없다. 자기 참조가 길이 비교를 가능하게 했고, 길이 비교가 모순을 만들었다.
강의의 마지막 한 발을 더 내디뎌, 회귀 정리가 빛을 발하는 또 다른 무대 — 수리논리학의 결정 문제 — 를 살핀다.
정의 11.7 (구조와 이론). 구조(structure)는 영역(universe)과 그 위의 함수·관계 기호의 해석으로 이루어진 수학 대상이다. 자연수 위의 덧셈만 가진 구조 (ℕ, +)와 덧셈·곱셈을 모두 가진 (ℕ, +, ×)을 떠올리자. 한 구조 𝔄의 이론(theory) Th(𝔄)는 𝔄에서 참인 1차 논리 문장(sentence) 전체의 집합이다.
"이 문장이 자연수에서 참인가?"라는 질문은 매우 자연스러운 결정 문제이다. 그 답은 — 놀랍게도 — 어떤 연산 기호를 허용하느냐에 따라 극과 극으로 갈린다.
정리 11.8 (Presburger, 1929). Th(ℕ, +)는 결정 가능하다.
덧셈만 있는 자연수의 1차 논리는 — ∀, ∃, ∧, ∨, ¬와 = 만 결합한 임의의 문장이라도 — 알고리즘으로 참·거짓을 판정할 수 있다. 증명은 양화사 제거(quantifier elimination)에 의존한다 — 모든 문장을 양화사 없는 문장으로 동치 변환할 수 있고, 양화사 없는 문장은 산술 식의 단순 검사로 끝난다.
정리 11.9 (Gödel·Tarski). Th(ℕ, +, ×)는 결정 불가능하다.
증명 직관. 곱셈이 더해지는 순간 우리는 1차 논리 안에서 튜링 기계의 계산 — 사실상 임의의 알고리즘 — 을 인코딩할 수 있게 된다. 핵심은 다음과 같다. 자연수의 쌍 ⟨a, b⟩, 시퀀스 (a1, ..., ak)를 단일 자연수로 번호 매기는 — 괴델 번호화(Gödel numbering) — 가 덧셈과 곱셈만으로 표현 가능하다. 이 번호화 위에서 "x는 M의 w에 대한 수락 계산 이력이다"라는 술어를 1차 논리식으로 적을 수 있다. 따라서 M이 w를 수락하는가 — 즉 ATM의 원소인가 — 는 "∃x: x는 수락 이력이다"라는 (ℕ, +, ×)의 문장의 진위와 동치이다.
이제 ATM ≤m Th(ℕ, +, ×) 환원이 완성되며, ATM의 결정 불가능성이 Th(ℕ, +, ×)로 그대로 전파된다. 회귀 정리는 보다 미묘한 곳에서 등장한다 — 괴델의 불완전성 정리에서 "이 문장은 증명 불가능하다"라는 자기 참조 문장을 만드는 데 사용되는 것이 정확히 우리의 SELF 보조정리의 산술 버전이다. ∎
덧셈만으로는 부족하지만 곱셈을 한 방울 더하는 순간 — 산술은 알고리즘의 모든 능력을 빨아들인다. 이 비대칭은 수학사의 가장 깊은 신비 중 하나이고, 괴델의 1931년 논문이 던진 충격의 본질이기도 하다. 학부 강의에서는 이 결과를 그저 풍문으로 듣게 되지만, 그 핵심 기계 장치는 이미 우리 손 안에 있다 — 환원, 계산 이력, 회귀 정리. 이 셋이 모이면 괴델의 정리가 보인다.
강의 9에서 11까지의 흐름을 한 문장으로 요약하면, "결정 불가능성은 한 점에서 시작해 환원으로 퍼지고, 자기 참조에서 절정에 닿는다"이다. 콰인이라는 작은 장난감이 어떻게 괴델의 결과까지 끌어내는지 보았다. 다음 강의부터는 시선을 결정 가능한 영역으로 다시 돌려 — 결정 가능하지만 얼마나 효율적으로 결정 가능한가 — 라는 새로운 질문, 즉 복잡도 이론(complexity theory)으로 들어간다.