순서를 거꾸로 뒤집어 박아 넣는다 — 튜링 차수를 아서-니무에-머를린 차수에 매장한 논문

2026년 11월 5일, arXiv에 18쪽짜리 짧은 논문 하나가 올라왔다. 제목은 「튜링 차수를 아서-니무에-머를린 차수 속으로 순서를 뒤집어 매장하기」. 저자는 장 아부 삼라(Jean Abou Samra)와 다비드 A. 마도르(David A. Madore) 두 사람이고, 분류는 수리논리학(math.LO)과 컴퓨터과학 논리(cs.LO)에 나란히 걸려 있다. 논문은 CSL 2027에 채택된 컨퍼런스 판본이며, 더 긴 원본 arXiv:2603.19946의 주요 결과만 추린 축약판이라고 스스로 밝힌다.

세 사람 이름이 붙은 차수

수리논리학에서 차수(degree)란 계산 능력의 등급표다. 가장 오래된 것이 튜링 차수로, 두 문제 A와 B가 서로를 오라클로 불러 풀 수 있으면 같은 차수에 속한다고 본다. 이 등급표는 부분순서를 이루는데, 대개 A가 B보다 쉽다는 방향으로 읽는다.

논문이 다루는 아서-니무에-머를린 차수(Arthur-Nimue-Merlin degrees)는 이 튜링 차수의 일반화다. 논문에 따르면 키하라(Kihara)가 도입한 개념으로, 유효 토포스(effective topos) 위의 라우베어-티어니 위상들이 이루는 부분순서집합 — 같은 말로 그 토포스의 부분토포스들의 격자 — 을 손에 잡히는 방식으로 묘사하려는 시도에서 나왔다. 격자나 위상 같은 추상적인 대상에 계산 가능성의 언어로 이름표를 붙이는 셈이다.

오라클 질의에 천사와 악마를 넣는다

이 차수의 정의는 세 명의 플레이어가 벌이는 게임이다. 핵심은 오라클에 질문을 던지는 과정에 두 종류의 비결정성을 동시에 집어넣는다는 점이다. 논문은 이를 천사적(angelic) 비결정성과 악마적(demonic) 비결정성이라고 부른다. 한쪽은 답이 존재하기만 하면 좋은 쪽으로 골라 주는 식이고, 다른 쪽은 어떤 답이 와도 견뎌야 하는 식이다.

보통의 계산 가능성 이론에서 오라클은 그냥 정답을 즉시 돌려주는 검은 상자다. 여기에 선택의 주체를 둘로 쪼개 넣으면, 같은 질문이라도 누가 고르느냐에 따라 가능한 계산의 범위가 달라진다. 순서 이론의 대상이었던 격자를 게임의 규칙으로 다시 적은 것이 이 정의의 요점이라고 논문은 설명한다.

상태 다섯 개짜리 튜링 기계의 상태 전이도 — Sn KGS, CC BY-SA 4.0 (Wikimedia Commons, File:Example of a Turing machine.svg)

논문이 실제로 구성한 것

여기서 이 논문의 주 결과가 나온다. 저자들은 튜링 차수 전체를 아서-니무에-머를린 차수 속으로 옮기되, 순서를 뒤집어서 옮기는 매장(embedding)을 구성한다고 밝힌다. 매장이므로 서로 다른 튜링 차수는 서로 다른 자리로 가고, 원래의 순서 관계는 보존된다. 다만 방향이 반대다.

이렇게 옮겨진 상(像)에 저자들은 co-튜링 차수라는 이름을 붙인다. 이름 그대로 역방향 사본이다. 그리고 여기서 끝내지 않고, 이 co-튜링 차수들이 아서-니무에-머를린 차수 안에서 자연스럽게 매장된 원래의 튜링 차수들과 어떤 순서 관계를 맺는지를 이어서 연구한다고 논문은 적는다. 두 사본이 나란히 놓였을 때 어느 쪽이 위로 올라가는지가 다음 질문이 된다.

왜 뒤집힘이 반직관적인가

직관적으로 계산 능력의 등급표는 더 어려운 문제일수록 위라는 방향으로 그려진다. 그런데 이 논문은 그 등급표를 통째로 뒤집은 채 다른 구조 안에 심는다. 뒤집힌 사본이 원본과 같은 구조 안에 공존한다는 것은, 하나의 격자 안에 서로 반대 방향을 가리키는 두 개의 좌표계가 들어 있다는 뜻이 된다.

원소 세 개짜리 집합의 멱집합이 이루는 격자의 하세 도해 — KSmrq, CC BY-SA 3.0 (Wikimedia Commons, File:Hasse diagram of powerset of 3.svg)

이런 구조는 흔히 위상이나 논리학에서 대칭이나 이중성의 형태로 나타난다. 다만 논문이 흥미롭게 보는 지점은 대칭이 아니라 비대칭의 정도다. 두 사본이 완전히 대칭이라면 뒤집힘은 별 정보를 주지 않는다. 두 사본이 어긋나는 지점이 곧 이 일반화된 차수가 원래의 튜링 차수보다 더 많이 담고 있는 정보라고 볼 수 있다.

여기에 계산 가능성 이론 쪽에서 자주 나오는 반사실적 질문이 겹친다. 오라클을 하나 더 붙이면 풀리는 문제와, 오라클을 바꿔도 난이도가 그대로인 문제는 서로 다른 층에 있다. 순서 역전 매장은 그 층의 배열 자체를 다른 격자에 사영하는 작업이므로, 어느 문제가 어느 층에 남는지가 곧 이 구성의 내용이 된다.

떠오르는 반론들

가장 먼저 나올 반론은 그럼 그냥 격자의 대칭성을 다시 적은 것 아닌가라는 것이다. 유효 토포스의 부분토포스 격자는 이미 알려진 대상이므로, 순서 역전 매장이 그 구조의 재서술에 그칠 수도 있다. 논문은 이 반론을 정면으로 다루지는 않지만, co-튜링 차수와 자연 매장된 튜링 차수의 관계를 따로 계산하는 것으로 그 물음에 답하려는 구성으로 읽힌다.

두 번째 반론은 매장의 보존성에 관한 것이다. 순서를 뒤집어 옮겼다면 원래 차수의 구조적 성질 — 상한과 하한의 존재 같은 — 이 그대로 살아남는지 확인해야 한다. 매장은 관계를 보존하지만 모든 연산을 보존하지는 않기 때문이다. 이 지점은 짧은 판본보다 원본 논문에서 더 자세히 다뤄질 것으로 보인다.

세 번째는 게임 정의의 해석 문제다. 천사적 비결정성과 악마적 비결정성을 한 게임에 같이 넣으면, 승패 조건을 어느 순서로 읽느냐에 따라 차수의 순서가 달라질 수 있다. 논문은 세 플레이어 게임이라는 틀을 명시하지만, 그 틀이 유일한 자연스러운 선택인지는 별도의 논증이 필요한 부분이다.

논문이 스스로 인정한 한계

가장 분명한 한계는 이 글이 축약판이라는 점이다. 논문은 제목에 short version을 달고, 주요 결과에 초점을 맞춘 컨퍼런스 판본이라고 명시한다. 18쪽이라는 분량도 그 방침과 맞물린다. 증명의 세부나 주변 정리들은 원본 arXiv:2603.19946을 봐야 한다.

또 하나 분명한 것은 이 결과가 계산 가능성 이론이나 실용적 알고리즘에 곧바로 쓰이는 종류가 아니라는 점이다. 유효 토포스와 위상, 격자라는 언어로 쓰인 결과이고, 독자층도 수리논리학과 범주론 쪽이다. 논문은 그 범위를 넘어서는 응용을 주장하지 않는다.

독자에게 던지는 질문

순서를 뒤집어서 같은 구조 안에 심는다는 발상은 수학에서 낯설지 않다. 문제는 그 뒤집힌 사본이 얼마나 많은 정보를 나르느냐다. 만약 뒤집힌 사본이 원본과 거의 겹친다면 우리는 새로운 것을 얻지 못한 것이고, 크게 어긋난다면 그 어긋남 자체가 새로운 불변량이 된다.

여러분이라면 이 게임에서 어느 플레이어에 베팅하겠는가. 답이 있으면 골라 주는 천사와, 무슨 답이 와도 견디는 악마 중 계산 능력의 등급을 더 크게 흔드는 쪽은 어느 쪽일까. 논문의 구성은 그 답을 격자의 모양으로 돌려준다.

참고 자료

Jean Abou Samra, David A. Madore, 「An order-reversing embedding of Turing degrees into Arthur-Nimue-Merlin degrees (short version)」, arXiv:2611.08319v1 [math.LO], 2026년 11월 5일. https://arxiv.org/abs/2611.08319

원본(장판): arXiv:2603.19946. 컨퍼런스 판본은 CSL 2027 채택.