6장 — 끝나지 않는 계산의 분류학

이 장에서 배우는 것 — 4장에서 우리는 골드바흐와 콜라츠가 "반례를 확인하는 방식"부터 다르다는 것을 손 논증으로 보았다. 이 장은 그 차이에 정확한 이름과 좌표를 붙이는 학문, 계산가능성 이론을 만난다. 계산의 수학적 정의인 튜링 기계, "끝나지 않음"을 미리 알 수 없다는 정지 문제, 문제의 어려움을 등급화하는 두 개의 사다리(산술적 위계와 튜링 차수), 그리고 "무한을 유한 시간에 아는 도구"의 정확한 가격표인 Busy Beaver의 $S(n)$과 $\Sigma(n)$가 새로 등장한다. 블로그가 "아직 없다"고 진단한 메타 학문이 사실은 1936년부터 존재해 왔다는 것 — 그러나 그 직관이 겨눈 과녁(마틴 추측, $S(6)$의 콜라츠형 병목)은 지금도 정말로 열려 있다는 것이 이 장의 결론이다.

들어가며 — 이제 그 차이에 이름을 붙인다

4장의 마지막 갈림길을 한 문단으로 되감아 보자. 골드바흐 추측("4 이상의 모든 짝수는 두 소수의 합이다")에 반례가 있다면 — 두 소수의 합으로 쓸 수 없는 짝수 하나가 있다면 — 그 짝수 이하의 소수 쌍을 전부 검사하는 유한한 계산만으로 반례임이 확정된다. 반면 콜라츠 추측의 반례가 '1에 도달하지 않고 무한히 커지는 발산 궤도'라면, 그 궤도를 아무리 오래 지켜보아도 "아직 안 내려온 것"인지 "영원히 안 내려오는 것"인지 유한 시간 안에 확정할 수 없다. 하나는 반례 확인이 유한한 문제이고, 하나는 반례 확인 자체가 무한을 요구할 수 있는 문제다. 4장에서는 이것을 손 논증으로만 보았다. 이제 그 차이에 이름을 붙인다.

이 장의 주인공은 블로그의 가장 야심 찬 제안이다. 저자는 무한을 "끝나지 않는 계산"으로 읽고(글 7), 수학의 난제를 "반례 탐색 프로그램의 정지 문제"로 환원한 뒤(글 9, 25), "칸토어가 무한을 등급화했듯 거듭되는 변환(프로그램)을 유형화하는 메타 학문"을 제안했다(글 9). 글 22는 "무한의 분류"를 직접 시도했고, 글 24는 "무한한 시간 뒤의 일을 유한한 시간 안에 아는 도구"를 꿈꿨다.

한 줄 결론부터 말하겠다. 저자가 "아직 없다"고 본 그 메타 학문은 1936년 이래 계산가능성 이론(computability theory)이라는 이름으로 존재하며, 그 안에 두 개의 '칸토어식 등급 체계' — 산술적 위계와 튜링 차수 — 가 이미 정밀하게 구축되어 있다. 그러나 이것은 실망할 이야기가 아니다. 저자의 직관이 진짜 열린 문제와 만나는 지점도 뚜렷하기 때문이다. 절반은 이미 있고, 나머지 절반은 정말로 없다 — 즉 미해결이다. 이 장이 끝날 때 그 경계선이 지도 한 장으로 정리된다.

이 자들은 한꺼번에 등장하지 않았다. "모든 문제를 푸는 절차가 있는가"가 무너진 뒤에도 수학자들은 포기하지 않고, 불가능성의 등급·프로그램 의미의 판정 한계·자연스러운 변환의 분류·작은 기계의 실행 기록이라는 새 질문을 차례로 만들었다.

연구 계보 | 질문이 어떻게 자랐는가

계산이란 무엇인가 — 규칙표와 무한 두루마리

"프로그램의 정지 여부"를 수학의 정리로 다루려면, 먼저 "프로그램"과 "계산"이 수학적 대상이어야 한다. 1936년, 24세의 앨런 튜링이 내놓은 답은 놀랄 만큼 소박한 장난감이었다. 연필과 지우개를 들고 격자 칸이 그려진 아주 긴 종이 두루마리 앞에 앉은 사람을 상상하자. 그는 한 번에 한 칸만 보고, 머릿속에 든 유한한 규칙 몇 줄에 따라 그 칸의 기호를 고쳐 쓰고 옆 칸으로 이동한다. 튜링의 주장은, 인간이든 기계든 '계산'이라 부를 만한 모든 절차가 이 장면으로 환원된다는 것이다.

여기서 결정적인 관찰 하나. 규칙표는 유한한 기호열로 받아 적을 수 있고, 기호열은 (예컨대 2진수로 읽으면) 자연수 하나다. 즉 프로그램도 데이터다 — 모든 튜링 기계에 번호(괴델 번호)를 매길 수 있다. 튜링은 여기서 한 걸음 더 나아갔다. 다른 기계의 번호를 입력으로 받아 그 기계의 실행을 그대로 흉내 내는 보편 기계(universal machine)가 존재한다. 오늘의 언어로는 인터프리터다. 정리 튜링(1936)은 이렇게 계산하는 기계의 수학적 정의, 보편 기계의 존재, 그리고 기계의 무한 거동을 미리 판별하는 일반 절차의 불가능성을 한 편의 논문에서 한꺼번에 세웠다.

왜 하필 이 장난감이 '계산'의 정의 자격을 갖는가? 같은 시기에 전혀 다른 정의들 — 처치의 람다 계산, 괴델–에르브랑의 재귀함수 — 이 제안되었는데, 검사해 보니 전부 튜링 기계와 정확히 같은 함수들을 계산했다. 그래서 "계산 가능하다 = 튜링 기계로 계산 가능하다"로 삼자는 것이 처치–튜링 명제(Church–Turing thesis)다. '정리'가 아니라 '명제(테제)'라 부르는 이유는, 이것이 증명의 대상이 아니라 "우리의 직관적 '계산' 개념을 이 정의가 온전히 포착한다"는 정의의 적절성에 대한 주장이기 때문이다. (물리 세계가 튜링 기계를 넘어서는 계산을 허용하는가라는 물리적 버전은 8장의 주제다.) 그리고 5장에서 "자릿수를 출력하는 프로그램이 존재하는 수"로 소박하게 정의했던 계산 가능 실수의 그 '프로그램'이 정확히 이 기계다 — 5장의 약속이 여기서 갚아진다.

정지 문제 — "끝나지 않음"은 반증 가능하지만 검증 불가능하다

이제 이 장의 첫 번째 큰 정리를 만날 차례다. 질문은 이렇다. 임의의 프로그램 $p$와 입력 $x$를 받아 "p를 x에 대해 실행하면 언젠가 멈추는가?"를 항상 유한 시간 안에 정확히 답하는 단 하나의 프로그램 — 만능 정지 판별기 — 이 존재하는가? 소프트웨어 엔지니어라면 누구나 갖고 싶은 도구다. 이런 무한 루프 검출기가 있다면 테스트와 검증은 얼마나 쉬워지겠는가.

정리 튜링(1936): 그런 판별기는 존재하지 않는다. 정확한 진술은 이렇다 — 정지 집합(실행이 언젠가 멈추는 (프로그램, 입력) 쌍 전체의 집합)은 계산가능 열거 가능(c.e.)하지만 계산가능하지 않다. 용어는 잠시 뒤에 풀기로 하고, 먼저 귀속에 관한 한정어 하나. 튜링이 1936년 논문에서 직접 증명한 것은 인쇄 문제·순환 판정의 결정불가능성이고, 오늘날 표준이 된 '정지 문제'라는 정식화와 명칭은 데이비스(1958)에서 정착했다. 여기서 "결정가능(decidable)하다"는 모든 경우에 유한 시간 안에 예/아니오를 정확히 답하는 프로그램이 존재한다는 뜻이고, 그런 프로그램이 없으면 결정불가능(undecidable)이다.

증명의 뼈대는 5장에서 만난 칸토어의 대각선 논법 그대로다. 만능 판별기 $H(p, x)$가 존재한다고 가정하자. $H$를 부품 삼아 심술궂은 프로그램 $D$를 하나 작성한다. $D$는 프로그램 번호 $p$를 입력받아 $H(p, p)$를 호출한다 — 즉 "$p$를 자기 자신의 코드에 대해 실행하면 멈추는가?"를 묻는다. 답이 "멈춘다"면 $D$는 일부러 무한 루프에 들어가고, "안 멈춘다"면 $D$는 즉시 멈춘다. 이제 $D$에게 $D$ 자신의 번호를 먹여 보자. $D(D)$가 멈춘다면 그것은 $H(D,D)$가 "안 멈춘다"고 답했기 때문인데, $H$는 늘 옳다고 가정했으므로 $D(D)$는 멈추지 않아야 한다. 반대로 $D(D)$가 멈추지 않는다면 $H(D,D)$는 "멈춘다"고 답했을 것이고, 같은 이유로 $D(D)$는 멈춰야 한다. 어느 쪽이든 모순이다. 따라서 $H$는 애초에 존재할 수 없다.

여기서 잠깐, 왜 이것이 놀라운지 짚고 가자. 정리의 두 얼굴을 눈높이로 다시 읽으면 — "멈춘다"는 쪽은 쉽다. 실제로 돌려 보면 되고, 멈추는 순간 확정된다. 어려운 것은 "멈추지 않는다"는 쪽이다. 저자가 말한 "끝나지 않는 계산"이라는 무한은 반증 가능하지만(멈추는 순간 반증된다) 검증 불가능한(영원히 지켜봐도 확정되지 않는) 사건이며, 이 비대칭이 이 이론 전체의 엔진이다.

반례 탐색기가 사는 방 — $\Pi^0_1$ 문장

저자의 환원이 완전히 옳은 자리부터 확인하자. 정리 "모든 $n$에 대해 $R(n)$이 성립한다"($\forall n\, R(n)$) 꼴의 문장 — 단, $R$은 각 $n$마다 유한 검사로 판별되는 결정가능 술어(술어란 각 입력마다 참/거짓이 정해지는 조건이다) — 를 $\Pi^0_1$ 문장이라 부른다(기호의 체계적인 도입은 다음 절에서 한다). 이런 문장은 반례 탐색기와 완벽하게 짝을 이룬다. $n = 1, 2, 3, \dots$을 차례로 검사하다가 $R(n)$이 거짓인 $n$을 만나면 멈추는 프로그램을 짜면, 문장이 거짓일 때에만 탐색기가 멈춘다. 저자의 "추측 = 반례 탐색 프로그램의 정지 여부"(글 9, 25)는 $\Pi^0_1$ 문장에 대해 완전히 옳다. 골드바흐가 전형이다 — 거짓이면 반례 탐색기가 정지하고, 참이면 영원히 돈다.

이 환원은 사고 실험 수준이 아니라 극단적으로 구체화되어 있다. 골드바흐가 거짓일 때에만 정지하는 27-상태 튜링 기계(2016)가 실제로 만들어져 있고, 25-상태 기계가 Lean 4로 형식 검증되었다. 리만 가설(3장)도 — 겉보기에는 복소평면 위 영점의 이야기지만 — $\Pi^0_1$ 문장으로 고쳐 쓸 수 있음이 증명되어 있어서, 744-상태 기계의 비정지와 동치다. 세계에서 가장 유명한 두 난제가 각각 "이 작은 기계는 영원히 멈추지 않는다"라는 문장과 논리적으로 같다는 뜻이다.

그러나 — 여기가 4장에서 예고한 교정 지점이다 — 콜라츠는 이 방에 살지 않는다. 콜라츠 추측은 $\forall n\, \exists k\, (T^k(n) = 1)$ 꼴의 문장이다. 말로 읽으면 "모든 양의 정수 $n$에 대해, 어떤 반복 횟수 $k$가 있어 콜라츠 사상 $T$(4장)를 $k$번 적용하면 1이 된다". 안쪽의 "$\exists k$"에는 미리 계산할 수 있는 상한이 없다. 반례가 '발산 궤도'라면 그 발산 자체가 유한하게 확인 불가능하므로, 반례 탐색기가 영원히 돌아도 추측이 참인지 알 수 없다. 콜라츠는 $\Pi^0_2$ 문장이며, $\Pi^0_1$로 표현된다고 알려져 있지 않다. 글 9에서 콜라츠와 골드바흐를 같은 유형으로 묶은 것은 이 지점에서 교정이 필요하고 — 바로 이 교정이 위계 이론의 존재 이유다. "추측마다 반례 탐색의 논리적 모양이 다르다"는 이 사실 자체가, 저자가 원한 '프로그램 유형화'의 첫 번째 실제 사례다.

산술적 위계 — 무한 검사의 중첩 깊이를 재는 자

방금 $\Pi^0_1$과 $\Pi^0_2$라는 두 개의 방을 보았다. 이제 건물 전체를 소개한다.

이 자로 재면 다음 좌표들이 나온다. 정지 문제는 $\Sigma^0_1$-완전, "모든 입력에서 정지하는가"(TOT)는 $\Pi^0_2$-완전, 골드바흐와 리만 가설은 $\Pi^0_1$, 쌍둥이 소수 추측과 콜라츠는 $\Pi^0_2$, 그리고 컴퓨터과학 최대의 미해결 문제인 $P \ne NP$("빠르게 검산되는 문제는 빠르게 풀리기도 하는가"를 부정하는 추측)조차 $\Pi^0_2$ 문장으로 쓸 수 있다. 여기서 '완전(complete)'은 그 등급의 대표 최난 문제라는 뜻이다 — 등급 안의 모든 문제를 유한한 번역 절차로 그 문제로 바꿀 수 있어서, 그것 하나가 풀리면 등급 전체가 풀린다.

정리 그리고 이 위계의 포함은 진성이다 — 층이 올라갈 때마다 아래층에서는 풀 수 없는 문제가 반드시 새로 생기고, 사다리는 끝없이 올라간다. 칸토어가 크기의 무한을 등급화했듯(5장), 이 위계는 '검증에 필요한 무한 검사의 중첩 깊이'로 문제의 논리적 복잡도를 등급화한다. 저자가 글 22에서 시도한 "무한의 분류"의 표준 지도가 정확히 이것이다.

오라클과 튜링 차수 — '풀 수 없음'에도 등급이 있다

그런데 왜 하필 한정사의 교대 횟수가 어려움의 자가 되는가? 그 답을 주는 장치가 오라클이다. 오라클(oracle, 신탁)은 특정 집합에 대한 질문("이 수가 그 집합의 원소인가?")에 공짜로, 즉시, 항상 정확히 답해 주는 가상의 부속 장치다. 오라클 $A$를 장착한 튜링 기계는 계산 도중 $A$에 대한 질문을 마음껏 던질 수 있다.

오라클은 사다리를 만든다. 보통 기계의 정지 문제를 $\emptyset'$(읽기는 "제로 점프" 또는 "제로 프라임")이라 하자. 정지 문제를 오라클로 장착한 기계는 훨씬 강력하지만, 그 기계들에 대한 정지 문제 $\emptyset''$가 다시 생기고, 이것은 $\emptyset'$ 오라클로도 풀 수 없다. 같은 재귀가 끝없이 반복된다($\emptyset', \emptyset'', \emptyset''', \dots$). 포스트의 정리가 이 사다리를 산술적 위계와 정확히 붙인다: 한정사 깊이 = 정지 문제라는 오라클을 몇 겹 쌓아야 풀리는가. '무한 검사'를 한 겹 유한화해 주는 오라클을 도입해도 그 오라클에 대한 정지 문제가 다시 생기는 이 재귀는, 5장에서 멱집합 연산($|X| < |2^X|$)이 $\aleph$의 사다리를 끝없이 밀어올리던 것과 구조적으로 평행하다.

문제들 사이의 상대적 난이도를 직접 재는 자도 있다. $A \le_T B$ — "$B$를 오라클로 쓰면 $A$를 풀 수 있다" — 라고 쓰고, 서로 환원되는 문제들을 하나의 등급으로 묶은 것이 튜링 차수다: '풀 수 없음의 정도'들의 반순서(모든 쌍이 서로 비교되지는 않는 순서 — 아래 '비교 불가능한 쌍'이 그 뜻이다). 정리 차수는 $2^{\aleph_0}$개 존재하고, 서로 비교 불가능한 차수 쌍이 있으며(클레이니–포스트 1954), 프리드버그(1957)와 무치니크(1956)는 결정가능 등급 $\mathbf{0}$과 정지 문제 등급 $\mathbf{0}'$ 사이에 중간 c.e. 차수가 존재함을 증명했다.

잠깐 멈춰서, 방금 문장에 이어지는 사실을 천천히 읽어 보자 — 이 장에서 가장 이상한 대목이다. 중간 차수는 존재한다. 그런데 그 중간 차수들은 대각화로 '제작'된 인공물이며, 수학의 자연스러운 결정불가능 문제 — 대각화 장치 없이 수학 실무에서 저절로 만나는 문제 — 중 중간 차수를 갖는 것은 하나도 알려져 있지 않다. 문제의 우주에 층은 비가산적으로 많은데, 자연은 그중 몇 개의 층에만 입주하는 것처럼 보이는 것이다. 이 현상을 설명하려는 것이 추측 마틴 추측이다. 이 추측은 아무 반복 변환이나 다루지 않고, 튜링 차수 위에서 차수를 존중하는 정의 가능한 함수라는 특수한 대상을 분류한다.

정리 Lutz–Siskind는 튜링 차수 위 순서 보존 함수에 대해 Martin 추측 Part 1을 증명했고, 측도 보존 함수에 대해서도 Part 1 결과를 세웠다(2025 JAMS). 여기서 Part 1은 해당 함수가 거의 모든 차수에서 상수이거나 입력 차수 이상이라는 첫 번째 이분법이다. 이는 전체 Martin 추측의 증명이 아니며, 블로그가 말하는 일반적인 "모든 변환 유형화"에 대한 정리도 아니다. 블로그 직관과 만나는 지점은, 먼저 대상·동치관계·허용 함수·정의가능성을 고정해야 분류 질문이 수학이 된다는 방법론이다.

Busy Beaver — 무한을 유한 시간에 아는 도구의 가격표

이제 글 24의 꿈으로 가자. "무한한 시간 뒤의 일을 유한한 시간 안에 아는 도구"(글 24) — 이것을 문자 그대로 수학화한 것이 라도(1962)의 Busy Beaver 함수다.

$S$가 왜 "무한을 유한 시간에 아는 도구"인가? $S(n)$의 값을 하나 알면 모든 $n$-상태 기계의 정지 여부가 유한 절차로 바뀐다. 기계를 $S(n)$스텝까지만 돌려 보라 — 그 안에 멈추지 않았다면, 정의에 의해, 영원히 멈추지 않는다. 무한히 기다려야 알 수 있던 사건이 유한한 마감 시한을 얻는다. 그래서 $S(27)$을 알면 골드바흐가, $S(744)$를 알면 리만 가설이 해당 명시 기계 구성 아래 기계적으로 판정된다. 저자가 원한 '무한 검사의 기계적 유한화'는 스텝형 $S$에 집약된다.

물론 공짜가 아니다 — 이 도구가 실패하는 지점도 정확히 계량되어 있다. 정리 첫째, $S$는 계산 불가능하고 모든 계산가능 함수를 지배한다(라도 1962): 어떤 계산가능 함수 $f$를 가져와도 충분히 큰 $n$부터는 $S(n) > f(n)$이다. $S$를 계산하는 프로그램이 있다면 방금 본 마감 시한 절차로 정지 문제가 풀려 버린다. 3장에서 만난 콜모고로프 복잡도 $K(x)$가 '서술의 최소 비용'을 재는 계산 불가능한 자였다면, $S(n)$은 '$n$개 상태짜리 프로그램이 낼 수 있는 최대 실행 예산'을 재는 계산 불가능한 자다.

정리 둘째 — 안전하게 검증된 핵심 이정표는 7,910상태다. Yedidia–Aaronson은 ZFC가 무모순이면 ZFC가 그 기계가 영원히 돈다는 사실을 증명할 수 없는 명시적 7,910상태 기계를 제시했다. 따라서 같은 무모순성 가정 아래 ZFC는 스텝형 $S(7910)$의 특정 정확한 값을 증명할 수 없다. 이것은 "참과 거짓 양쪽이 모두 독립"이라는 말이 아니라, 해당 정지 사실과 정확한 마감값에 대한 증명 불가능성 방향의 결론이다.

Riebel은 구성을 745상태로 줄였지만, 원 정리는 NQL 컴파일러(745상태 기계의 규칙표를 생성하는 번역 프로그램)와 생성 코드가 모두 버그가 없다는 조건부이고 그 구현의 형식 검증이 남아 있다고 명시한다. 그러므로 745상태는 중요한 축소 이정표이되, 무조건적인 정리나 최신 최소 기록으로 쓰지 않는다. 공리계의 한계가 거대한 무한집합만이 아니라 유한 상태 기계가 정의하는 자연수에도 닿는다는 교훈은 안전한 7,910상태 결과만으로도 충분하다.

현재 전선은 살아 있는 드라마다. bbchallenge 협업은 2024년에 계산과 Coq 형식 검증을 완료·공개했고, 2025년 원논문에서 181,385,789대의 기계를 판정하여 $S(5) = 47{,}176{,}870$임을 증명했다. 프로젝트 완료 시점과 학술 논문 연도를 한 날짜로 뭉치지 않는 것이 중요하다. 반면 $S(6)$은 2024년 발견된 'Antihydra'라는 6-상태 기계의 정지 여부와 연결된 병목을 포함한다. 이 기계의 거동은 $h \mapsto h + \lfloor h/2 \rfloor$ 반복의 홀짝 조건을 추적하는 콜라츠형 궤적이다. 더 큰 하한 기록은 계속 갱신되는 최신성 항목이므로 기준 날짜와 원출처를 붙여 별도로 관리해야 한다.

$S(6)$ 전선에 콜라츠형 병목이 등장한다. 이는 저자가 글 9에서 콜라츠와 정지 문제를 함께 본 직관이 실제 연구 질문과 만나는 사례지만, 원래 3n+1 문제와 이 기계 사이의 직접 함의를 뜻하지는 않는다.

라이스 정리 — 자동 유형 판별기의 일반 한계

마지막 일반 정리는 저자의 제안 전체를 위에서 내려다보게 해 준다. 저자의 메타 학문이 "거듭되는 변환(프로그램)을 유형화"하는 학문이라면, 그 첫 도구는 프로그램을 받아 유형을 판별하는 자동 분류기일 것이다. 정리 라이스 정리(1953)가 이 분류기의 운명을 한 번에 결정한다: 프로그램이 계산하는 함수 — 코드의 생김새가 아니라 의미론적 행동 — 에 관한 어떤 비자명한 성질도 결정불가능이다. '비자명'은 모든 프로그램이 갖거나 아무 프로그램도 갖지 않는 자명한 성질을 제외한다는 뜻이다. "이 함수는 항상 0을 출력하는가", "이 두 프로그램은 같은 일을 하는가", "이 프로그램은 소수만 출력하는가" — 전부 판별 불가능하다. 저자가 꿈꾸는 '변환의 자동 유형 판별기'는 어떤 비자명한 유형 체계에 대해서도 존재할 수 없다.

그러나 이것이 분류학의 끝이 아니라는 것이 이 장의 반전이다. 계산가능성 이론은 결정불가능한 분류 문제들의 난이도를 다시 분류한다. "모든 입력에서 정지하는가"(TOT)는 $\Pi^0_2$-완전, "정지하는 입력이 유한 개뿐인가"(FIN)는 $\Sigma^0_2$-완전, "정지하지 않는 입력이 유한 개뿐인가"(COF)는 $\Sigma^0_3$-완전 — 판별 불가능한 성질마다 '얼마나 불가능한지'의 좌표가 붙는다. 저자의 메타 학문은 '프로그램을 유형으로 나누는 학문'이 아니라 '유형 판별의 불가능성의 정도를 나누는 학문'으로 실현되어 있다.

콜라츠형도 같은 방식으로 좌표를 받았다. 4장에서 결과로만 만난 사실 — 콘웨이(1972)가 콜라츠를 일반화한 함수 클래스(주기별 선형 분기 함수)의 궤도 도달 문제가 결정불가능임을 증명했고, 그런 함수족이 임의의 계산을 시뮬레이션할 수 있으며(콘웨이가 이 아이디어로 만든 FRACTRAN이라는 언어는 튜링 완전, 즉 보편 기계와 동등하다), 커츠–사이먼(2007)이 전칭 버전("모든 $n$이 1에 도달하는가")이 $\Pi^0_2$-완전임을 증명했다 — 의 정확한 주소가 이 위계다. 4장의 필수 주의를 한 줄로 재고지한다: 이것은 매개변수화된 클래스 전체에 대한 정리이지 3n+1이라는 특정 함수의 결정불가능성이 아니며, 콜라츠 추측 자체는 하나의 고정된 문장으로서 증명될 수도, 반증될 수도, 특정 공리계로부터 독립일 수도 있고 어느 쪽인지 알려져 있지 않다(콘웨이가 만년에 "콜라츠 자체도 증명 불가능하게 참일 수 있다"고 쓴 것은 사변이다). '분류학이 없는' 것이 아니라 '분류가 불가능함이 분류되어' 있는 것이다.

글 2와 글 19의 "수학 = 소프트웨어"라는 등식 아래에서 이 정리는 실무의 언어로도 읽힌다. 콜라츠가 어려운 이유와 소프트웨어 검증이 어려운 이유가 같은 정리에서 나온다 — 반례 탐색이 콜라츠를 확정하지 못하는 것과, 테스트가 "버그 없음"을 확정하지 못하는 것은 같은 벽의 양면이다.

증명의 등급화와 기계화 — 분류학은 실무가 되었다

분류된 것은 문제만이 아니다. 증명과 이론 자체도 등급을 받았다.

그리고 이 분류학은 지난 20년 사이 실무가 되었다. 다만 “컴퓨터가 수학을 했다”는 한 문장 안에는 서로 다른 역할이 섞이므로 네 갈래로 나누어 읽어야 한다.

Lean이나 Coq는 특히 “증명을 검사하는 컴파일러” 역할을 한다. 수학 증명을 형식 언어로 적으면 컴파일러가 타입 오류를 잡아내듯 논리의 빈틈을 검사한다. 글 4와 글 25의 전수 조사·Python 실험 제안도 정식 방법론의 한 부분이지만, 어느 역할에 속하는지와 증명까지 완료했는지를 함께 표시해야 한다.

같은 동전의 뒷면도 정확히 말해 두자. 골드바흐 추측의 전수 검증은 $4 \times 10^{18}$까지 완료되었다(Oliveira e Silva–Herzog–Pardi, 검증 완료 2013, Math. Comp. 2014 게재). 그러나 이것은 $\Pi^0_1$ 문장의 '유한 구간 유한화'일 뿐 증명이 아니다 — 전칭 문장은 유한 검사를 아무리 쌓아도 확정되지 않고, 반례를 만나 반증되는 길만이 유한하다. 이 한 문장이 전수 조사라는 방법론의 힘과 한계를 동시에 보여준다.

무엇이 증명되었고, 무엇이 열려 있는가

원문 리포트는 이 장의 내용 전체를 지도 한 장으로 요약했다. 저자의 구상 하나하나에 대해 "이미 존재하는 이론"과 "실제로 열려 있는 부분"을 대응시킨 표다. 먼저 배지부터 정리하고 표를 보자.

저자의 "아직 없다"는 진단은 절반만 수정하면 된다. 메타 학문은 90년째 존재하며, 이름은 계산가능성 이론이다. 그러나 저자의 직관이 향한 곳 — 조건을 고정한 자연스러운 차수 변환의 분류(마틴 추측), 콜라츠의 증명가능성, $S$ 전선의 콜라츠형 병목 — 은 2020년대 연구의 실제 최전선과 만난다.

6장 요약

• 튜링 기계는 "무한 테이프 + 유한 규칙표"라는 계산의 수학적 정의이고, 프로그램도 데이터이므로 모든 기계를 흉내 내는 보편 기계(인터프리터)가 존재한다. "계산 가능 = 튜링 기계로 계산 가능"이 처치–튜링 명제다(정리가 아니라 정의의 적절성 주장; 물리 버전은 8장).
• 정리 정지 문제: 정지 집합은 c.e.지만 계산가능하지 않다(튜링 1936, 명칭 정착은 데이비스 1958). "끝나지 않는 계산"은 반증 가능하지만 검증 불가능한 사건이고, 이 비대칭이 이론 전체의 엔진이다. 증명은 5장 대각선 논법의 재사용이다.
• 산술적 위계 $\Sigma^0_n/\Pi^0_n$은 한정사 교대 깊이로 문제를 등급화한다. 골드바흐·리만 가설은 $\Pi^0_1$(반례 탐색기 환원이 정확), 쌍둥이 소수·콜라츠는 $\Pi^0_2$(발산 반례는 유한 확인 불가). 포함은 진성이며, 포스트 정리가 "한정사 깊이 = 정지 오라클의 겹수"로 위계를 설명한다 — 멱집합이 $\aleph$ 사다리를 밀어올리는 것과 평행하다.
• 튜링 차수는 '풀 수 없음의 정도'의 등급이다. 정리 중간 c.e. 차수는 존재한다. 정리 Lutz–Siskind는 순서 보존·측도 보존 함수에 대해 Martin 추측 Part 1을 증명했다. 추측 전체 추측은 미해결이며 일반적인 모든 반복 변환의 분류 정리가 아니다.
• 정리 스텝형 $S(n)$은 "무한을 유한 시간에 아는 도구"의 완성형이자 그 가격표다. $S$는 계산 불가능하고 모든 계산가능 함수를 지배한다. 7,910상태 ZFC 한계는 안전한 정리, 745상태 축소는 구현 정확성 조건부다. bbchallenge는 2024년 계산·Coq 검증을 완료했고 2025년 논문에서 $S(5)$를 확정했다. $S(6)$에는 콜라츠형 병목이 남아 있다.
• 정리 라이스 정리: 프로그램의 비자명한 의미론적 성질은 전부 결정불가능 — 그래서 메타 학문은 '유형으로 나누는 학문'이 아니라 '유형 판별의 불가능성의 정도를 나누는 학문'으로 실현되어 있다.
• 형식 검증(Lean/Coq)과 전수 조사는 수학의 정식 방법론이 되었지만, 전수 검사는 $\Pi^0_1$ 문장의 유한 구간 유한화일 뿐 증명이 아니다.
• 다음 장 예고: 7장에서는 이 장의 튜링 기계가 '랜덤하다'는 개념 자체의 정의(마틴뢰프 랜덤성)가 되는 것을 본다.

세 문장으로 확인하기

쉬운 출구 — 직관 카드

깊은 출구 — 대학원으로 가는 길