Additive systems for $\mathbb{Z}$ are undecidable

이 논문은 정수 집합 $\mathbb{Z}$에 대한 **가법 시스템 (Additive Systems)**의 결정 가능성 (decidability) 문제를 다루며, 이를 동역학 시스템 (dynamical systems) 및 계산 이론 (computability theory)의 난제들과 연결하여 **결정 불가능성 (undecidability)**을 증명합니다.

저자 Andrei Zabolotskii 는 가법 시스템의 완전성 (completeness)을 판별하는 문제가 콜라츠 추측 (Collatz conjecture) 및 프랙트란 (Fractran) 의 보편적 정지 문제와 동치임을 보임으로써, 이 분야의 근본적인 한계를 규명했습니다.

다음은 논문의 상세한 기술적 요약입니다.

1. 문제 정의 (Problem Statement)

• 가법 시스템 (Additive System): 가환 모노이드 $M$ (주로 $\mathbb{N}_0$ 또는 $\mathbb{Z}$) 에 대해, 부분집합들의 집합 $\mathcal{A} = \{A_0, A_1, \dots\}$가 주어졌을 때, $M$의 모든 원소 $n$이 $n = a_0 + a_1 + \dots$ ($a_i \in A_i$, 유한개만 0 이 아님) 형태로 유일하게 표현될 수 있으면 $\mathcal{A}$를 $M$에 대한 가법 시스템이라고 정의합니다.
• 기존 연구 ($\mathbb{N}_0$): de Bruijn 의 정리에 의해 $\mathbb{N}_0$에 대한 가법 시스템은 완전히 분류되었습니다. 모든 가법 시스템은 '영국식 숫자 체계 (British number systems)'의 축소 (contraction) 로 표현됩니다.
• 핵심 문제 ($\mathbb{Z}$): 정수 전체 $\mathbb{Z}$에 대한 가법 시스템은 훨씬 더 복잡합니다. 기존 연구는 주로 두 집합의 직합 ($Z = A \oplus B$) 형태에 집중했으나, 무한한 개수의 집합을 포함하는 일반적인 경우의 완전성 판별은 미해결 상태였습니다.
• 질문: 주어진 집합들의 모임 (특히 정수 전체를 덮는지) 이 가법 시스템인지 여부를 알고 있는 알고리즘이 존재하는가?

2. 방법론 및 주요 개념 (Methodology & Key Concepts)

저자는 $\mathbb{Z}$에 대한 가법 시스템을 분석하기 위해 **정준 모임 (Canonical Collections)**이라는 새로운 개념을 도입하고, 이를 **비자율 동역학 시스템 (Non-autonomous dynamical systems)**의 관점에서 해석했습니다.

2.1 정준 모임 (Canonical Collections)

• 정의: 정수열 $(b_i)_{i \in \mathbb{N}_0}$ (기저, $b_i > 1$) 과 집합열 $(T_i)_{i \in \mathbb{N}_0}$로 구성되며, $T_i$는 $b_i$에 대한 완전 잉여계 (0 포함) 입니다.
  • 집합열: $A_0 = T_0, A_1 = b_0 T_1, A_2 = b_0 b_1 T_2, \dots$
  • 형태: $\{T_0, b_0 T_1, b_0 b_1 T_2, \dots\}$
• 완전성 (Completeness): 정준 모임의 직합이 $\mathbb{Z}$ 전체와 일치할 때, 이를 '완전한' 가법 시스템이라고 합니다.
• 특징: $\mathbb{N}_0$의 숫자 체계 (예: 10 진법) 를 $\mathbb{Z}$로 확장한 형태 (예: 음이진법, 균형 삼진법) 를 일반화한 것입니다.

2.2 동역학 시스템으로의 전환

• 정준 모임의 완전성 판별 문제는 정수 $n$의 '확장 (expansion)'이 유한한지 여부와 동치입니다.
• 매핑 (Mapping): 정수 $n$에 대해 $f_i(n) = \frac{1}{b_i}(n - t_i(n))$로 정의된 함수열을 적용합니다. 여기서 $t_i(n)$은 $n$을 $b_i$로 나눈 나머지 중 $T_i$에 속하는 유일한 원소입니다.
• 궤적 (Trajectory): $n \to f_0(n) \to f_1(f_0(n)) \to \dots$의 수열을 생성합니다.
• 핵심 명제 (Proposition 1): 정준 모임이 완전한 가법 시스템이 되기 위한 필요충분조건은 모든 정수 $n$에 대해 궤적이 결국 0 으로 수렴하여 상수가 되는 것입니다.

3. 주요 결과 (Key Results)

저자는 정준 모임의 완전성 판별 문제가 다음과 같은 유명한 난제들과 동치임을 증명했습니다.

3.1 콜라츠 추측과의 동치 (Theorem 1)

• 결과: 콜라츠 추측이 참인지 여부와 동치인 정준 모임 $A_C$가 존재합니다.
• 구현: $b_i = 4^{i+1}$로 설정하고, $f_i$ 함수가 콜라츠 함수 ($3n+1$ 또는 $n/2$) 와 유사하게 작동하도록 $T_i$를 설계했습니다.
• 의미: 만약 콜라츠 추측이 참이라면, 이 특정 정준 모임은 $\mathbb{Z}$를 덮는 완전한 가법 시스템이 됩니다. 반대로, 이 모임의 완전성을 증명하는 것은 콜라츠 추측을 증명하는 것과 같습니다.

3.2 Fractran 의 보편적 정지 문제와의 동치 (Theorem 2)

• Fractran: 존 콘웨이 (John Conway) 가 고안한 계산 이론에서 범용성을 가진 프로그래밍 언어입니다. 정수 입력에 대해 유리수 시퀀스를 곱하며 반복하는 과정을 거칩니다.
• 결과: Fractran 프로그램 $F$가 모든 입력에 대해 정지하는지 여부와 동치인 Fractran 타입 정준 모임 $A_F$가 존재합니다.
• 구현: 기저 $b_i$를 충분히 크게 설정하고, $f_i$ 함수를 Fractran 프로그램의 한 단계 실행과 동일하게 정의했습니다.
• 결론 (Corollary 2): 주어진 Fractran 프로그램에 해당하는 정준 모임이 완전한지 판별하는 문제는 **결정 불가능 (Undecidable)**합니다.
  • 이는 Church-Turing 정리에 의해 Fractran 의 정지 문제가 결정 불가능하므로, 가법 시스템의 완전성 판별 문제 또한 결정 불가능함을 의미합니다.

4. 의의 및 기여 (Significance & Contributions)

1. 결정 불가능성의 증명: 정수 $\mathbb{Z}$에 대한 가법 시스템의 완전성 판별 문제가 알고리즘적으로 해결 불가능함을 최초로 보였습니다. 이는 가법 조합론 (Additive Combinatorics) 분야에서 결정론적 접근의 한계를 보여줍니다.
2. 학제간 연결 (Interdisciplinary Connection):
   • 가법 조합론 (수열의 합집합 구조)
   • 동역학 시스템 (반복 함수의 궤적)
   • 계산 이론 (정지 문제, 콜라츠 추측)
   • 이 세 가지 분야를 '정준 모임'이라는 개념을 통해 통합하여, 수학적 난제들이 서로 어떻게 변환될 수 있는지를 보여주었습니다.
3. de Bruijn 정리의 한계 명확화: $\mathbb{N}_0$에서는 de Bruijn 정리가 모든 가법 시스템을 분류했지만, $\mathbb{Z}$에서는 그러한 완전한 분류가 불가능하며 (일반적인 가법 시스템이 정준 모임의 축소로 표현되지 않음), 그 판별 자체가 계산적으로 불가능할 수 있음을 보였습니다.
4. 새로운 연구 방향 제시: 가법 시스템의 구조를 동역학 시스템의 궤적 수렴 문제로 재해석함으로써, 난해한 조합론적 문제를 동역학적 관점에서 분석할 수 있는 새로운 프레임워크를 제시했습니다.

요약

이 논문은 정수 집합을 유일하게 표현하는 가법 시스템의 존재 여부를 판별하는 문제가, 콜라츠 추측과 Fractran 의 정지 문제와 동치임을 증명함으로써, 해당 문제가 **결정 불가능 (Undecidable)**함을 밝혔습니다. 이는 단순한 수론적 문제를 넘어 계산 이론의 근본적인 한계가 가법 조합론의 구조적 성질에 어떻게 내재되어 있는지를 보여주는 중요한 성과입니다.