무작위를 계산하는 것과 계산을 앞지르는 것 — 44년 된 등식에 금이 간 자리

2026년 11월 4일 12시 43분(UTC), arXiv의 수리논리(math.LO) 분류에 15쪽짜리 논문 한 편이 올라왔다. 제목은 「Escaping and generics over ideals」, 저자는 로랑 비앙브뉴(Laurent Bienvenu), 노암 그린버그(Noam Greenberg), 뤼도빅 파테(Ludovic Patey), 댄 투레츠키(Dan Turetsky) 네 명이다. 다루는 대상은 낯설지만, 출발점은 1982년까지 거슬러 올라가는 등식 하나다.

1. 44년 된 등식, 그리고 그 등식의 두 방향

계산가능성 이론에는 커츠(Kurtz)가 1982년에 남긴 결과가 있다. ‘약한 1-제네릭(weakly 1-generic) 집합을 계산할 수 있는 오라클’과 ‘모든 계산가능한 함수를 앞지르는 함수를 계산할 수 있는 오라클’이 정확히 같은 집합이라는 것이다. 제네릭 수열은 어떤 계산가능한 규칙도 피해가는, 다시 말해 ‘특별한 구조가 없는’ 수열이고, 탈출 함수(escaping function)는 어떤 계산가능한 함수보다도 무한히 자주 더 큰 값을 내는 함수다. 성격이 전혀 달라 보이는 두 대상이 같은 계산 능력을 요구한다는 이 등식은 이후 40년 넘게 인용되어 왔다.

논문은 이 등식을 의심하지 않는다. 대신 등식을 이루는 두 방향의 ‘성격’이 다르다고 본다. 제네릭 수열에서 탈출 함수로 가는 방향은 거의 자명하다. 약한 1-제네릭 수열 G와 계산가능한 함수 f가 주어지면, “어떤 위치 x에서 G(x) > f(x)인 문자열”들의 모임 D를 생각하면 된다. D는 조밀하고 계산가능하며, G가 D를 만나기만 하면 그 순간 G는 f를 앞지른다. 논문은 이 방향을 ‘본질적(essential)’이라고 부른다. 반면 반대 방향, 즉 탈출 함수에서 제네릭 수열을 뽑아내는 구성은 모든 계산가능 열거 집합을 균일하게 나열하는 장치에 기대고 있어서 상대적으로 ‘우연적(accidental)’이라는 것이다.

2. 만약 보편 기계를 빼앗는다면

이 직관을 형식화하는 방법이 ‘이데알(ideal) 위에서의 계산’이다. 튜링 이데알 I는 튜링 환원에 대해 아래로 닫혀 있고 유한 개의 원소를 합쳐도 다시 그 안에 남는 집합족이다. 스펙터(Spector)가 1956년 모든 가산 튜링 이데알이 ‘정확한 쌍(exact pair)’을 가진다는 것을 보였고, 프리드먼(Friedman)은 1974년 이데알이 역수학의 기초 이론에 대한 ω-모형의 2차 부분과 정확히 대응한다는 것을 보였다. 논문은 X ≤_I Y를 “어떤 Z ∈ I에 대해 X ≤_T Y ⊕ Z”로 정의하고, 이를 ‘I-계산가능’이라 부른다.

핵심은 이 정의가 단순한 일반화가 아니라는 점이다. I가 주 이데알(하나의 오라클로 생성되는 이데알)이 아니면, ‘I의 어떤 원소에 대해 계산가능 열거’라는 개념 전체를 균일하게 나열할 방법이 사라진다. 논문은 이 상황을 한 문장으로 요약한다. “이데알에 상대화된 계산은 보편 기계가 없는 계산이다(computability without a universal machine).” 앞 절에서 ‘우연적’이라고 불렀던 방향이 바로 이 보편 기계에 의존하고 있었으므로, 보편 기계를 빼앗으면 그 방향이 무너질 수 있다.

앨런 튜링, 1951년 — 엘리엇 앤 프라이(Elliott & Fry) 촬영, 퍼블릭 도메인 (Wikimedia Commons)

3. 실제로 무너진다 — 분리(separation)의 등장

논문의 주 결과 중 하나(정리 4.1)는 이 무너짐이 실제로 일어난다는 것을 보인다. 가산 튜링 이데알 I가 ‘DNC의 모형’일 때, 즉 I 안의 모든 원소 X에 대해 X-대각 비계산 함수(diagonally non-X-computable function)가 다시 I 안에 존재할 때, I는 ‘분리(separation)의 예’가 된다. 즉 I-탈출 함수이면서 I-약한 제네릭 집합은 하나도 I-계산하지 못하는 함수가 존재한다.

이것이 반직관적인 이유는, 탈출 함수가 원래 ‘무작위에 가까운 것’의 대표 선수로 소개되어 왔기 때문이다. 계산가능한 세계에서는 탈출하는 순간 제네릭이 공짜로 따라왔는데, 이데알을 조금만 풍부하게 만들면 그 공짜가 사라진다. 논문은 이를 두고 탈출에서 제네릭으로 가는 함의가 ‘본질적’이지 않다고 말한다. 등식의 한쪽은 계산의 힘에 대한 사실이고, 다른 쪽은 특정한 나열 장치가 우연히 제공해 준 선물이었다는 뜻이다.

4. 밀러 강제법, 그리고 생각보다 낮은 문턱

증명의 도구는 강제법(forcing)이다. 집합론에서 두 문제의 ‘세기’가 다르다는 것을 보일 때 쓰는 방법을, 논문은 계산가능성 이론의 언어로 옮긴다. 탈출 함수는 추가하되 제네릭 수열은 추가하지 않아야 하므로, 표준적인 선택지는 밀러 강제법(Miller forcing), 즉 모든 노드가 무한 분기를 갖는 유리 완전 트리(rational perfect tree)다. 기하라(Kihara)는 2018년 초산술적(hyperarithmetic) 집합들의 이데알이 이 강제법을 쓰기에 충분하다는 것을 보였는데, 이 논문은 그 문턱을 훨씬 낮춘다. 2-DNC의 모형이면 충분하다는 것(정리 3.3)이 이 논문의 기술적 성과다.

정리 3.3은 더 강한 형태로 진술된다. 임의의 가산 함수 모임 E에 대해, E의 모든 원소를 앞지르면서도 I-약한 제네릭 집합은 하나도 I-계산하지 못하는 함수가 존재한다. 논문은 이를 ‘강한 분리(strong separation)’라고 부른다. 함수 하나를 상대로 이기는 것이 아니라, 셀 수 있는 만큼의 함수 무리를 동시에 상대로 이긴다는 뜻이다. 흥미로운 것은 이 증명이 균일하지 않다는 점이다. 점프 이데알이 아닌 경우에는 무한 분기 대신 ‘I의 관점에서 유계가 아닌 만큼만’ 분기하는 유한 분기 트리를 써야 한다고 논문은 밝힌다.

5. 반대 방향 — 그렇다면 무엇이 분리를 만드는가

DNC가 분리를 보장한다면, DNC가 없을 때는 함의가 성립하는가. 정리 6.1은 부분적인 답을 준다. 가산 튜링 이데알 I가 분리의 예라면, I는 DNC의 모형이거나 HI(하이퍼면역, hyperimmune)의 모형이어야 한다. 증명의 뼈대는 스테판과 유(Stephan–Yu, 2006)가 특성화한 ‘약한 1-제네릭에 대한 낮음(lowness)’ 개념이다. “Z가 약한 1-제네릭에 대해 낮다”는 것은 Z의 정도가 계산가능하게 지배되고(computably dominated) DNC가 아니라는 조건과 동치다.

그런데 여기서 예상 가능한 다음 수가 있다. “그럼 DNC 또는 HI가 정확한 특성화인가?” 논문은 7절에서 그것도 아니라고 답한다. HI의 모형이면서 동시에 함의의 예인 이데알이 존재한다(명제 7.1). 즉 지금까지 확인된 조건들은 필요조건의 일부일 뿐, 충분조건도 필요충분조건도 아니다.

6. 왜 하필 이데알인가 — 이웃한 문제들

논문은 이데알 위 계산을 바이어슈트라스 문제(Weihrauch problem)와 연결한다. 지배 문제 Dom은 함수 f를 받아 f를 지배하는 함수를 내놓는 문제이고, 메이거 포획 문제 Capture(M)은 실수 x를 받아 x를 포함하는 메이거 집합을 내놓는 문제다. 전자에서 후자로 가는 강한 바이어슈트라스 환원이 존재하기 때문에, ‘제네릭 → 탈출’ 방향은 모든 이데알에서 성립한다. 논문은 이 환원이 집합론의 부등식 cov(M) ≤ 𝔡(메이거 덮개수가 지배수 이하)를 설명한다고 짚는다.

반대 방향에는 그런 환원이 없다. 정의 가능한 사상조차 없고, 실제로 어떤 이데알에서는 함의가 실패한다. 논문이 던지는 주 질문은 그래서 자연스럽다. “어떤 가산 튜링 이데알에서 탈출이 제네릭을 보장하는가.” 이는 ‘본질적 함의’와 ‘우연적 함의’를 구별하자는 처음의 직관을, 하나의 정리가 아니라 이데알의 분류 문제로 바꿔 놓은 것이다.

프랑스에서 제작된 교육용 전자 튜링 기계 모형 — Mdtcreator, CC BY-SA 4.0 (Wikimedia Commons)

7. 저자들이 스스로 인정한 한계

논문은 8절에서 두 개의 열린 질문을 남긴다. 첫째, 분리 이데알의 완전한 특성화(질문 8.1). 둘째, HI의 모형이면서 DNC의 모형이 아닌 이데알의 특성화(질문 8.2). 저자들은 “우리가 아는 한 DNC가 올바른 특성화일 수 있다”고 조심스럽게 적는다. 즉 정리 4.1은 충분조건을 주지만, 그것이 필요조건인지는 모른다는 것이다.

또 하나의 한계는 범위다. 결과는 모두 가산 튜링 이데알에 대한 것이고, 비가산 이데알이나 다른 환원 개념으로 옮겨질 때 무엇이 남는지는 다뤄지지 않는다. 증명이 균일하지 않다는 점, 그리고 강제법이 ‘충분히 닫힌’ 이데알을 전제한다는 점도 논문이 직접 밝히는 조건이다. 15쪽에 담긴 것은 완성된 분류표가 아니라, 분류가 가능하다는 증거와 그 분류가 만만하지 않다는 증거다.

8. 독자에게

이 논문이 흥미로운 이유는 수학 자체보다 그 태도에 있다. 40년 넘게 하나의 정리로 굳어 있던 등식을 ‘두 방향의 무게가 다르다’는 관찰로 다시 열고, 그 무게 차이를 이데알이라는 렌즈로 측정한다. 그리고 그 렌즈를 끼우자 등식의 한쪽이 우연에 가까운 것으로 드러난다.

만약 ‘무작위’라는 말에서 우리가 떠올리는 것이 계산 불가능성의 다른 이름일 뿐이라면, 계산의 틀을 조금만 바꿔도 그 이름은 다른 것을 가리키게 된다. 여러분은 무작위성을 대상의 성질로 보는 쪽인가, 아니면 우리가 가진 계산 장치에 대한 관계로 보는 쪽인가.

참고 자료

Laurent Bienvenu, Noam Greenberg, Ludovic Patey, Dan Turetsky, 「Escaping and generics over ideals」, arXiv:2611.06439 [math.LO], 2026년 11월 4일 제출, 15쪽. https://arxiv.org/abs/2611.06439

주요 인용: Kurtz (1982) 약한 1-제네릭과 탈출 함수의 정도 일치 · Andrews, Gerdes, Miller (2014) 약한 3-제네릭에 대한 반례 · Stephan & Yu (2006) 약한 1-제네릭에 대한 낮음의 특성화 · Kihara (2018) 초산술 이데알과 밀러 강제법 · Spector (1956) 가산 이데알의 정확한 쌍 · Friedman (1974) 이데알과 역수학.