Shannon meets Gödel-Tarski-Löb: Undecidability of Shannon Feedback Capacity for Finite-State Channels

1. 연구 문제 (Problem Statement)

이 연구의 핵심 질문은 다음과 같은 정확한 임계값 결정 문제가 알고리즘적으로 해결 가능한지 여부입니다.

• 입력:
  • 이진 입력/이진 출력, 유리수 (rational) 파라미터를 가지며, 단일 사역 (Unifilar) 특성을 가진 유한 상태 채널 $W_e$의 인코딩 $e$.
  • 지정된 유리수 초기 상태 분포 $\pi_{1,e}$.
  • 유리수 임계값 $q \in \mathbb{Q}$.
• 질문:
  • 해당 채널의 피드백 용량 $C_{fb}(W_e, \pi_{1,e})$가 임계값 $q$ 이상인지 여부는 결정 가능한가?
  • 즉, 술어 $Cap(e, q) \iff C_{fb}(W_e, \pi_{1,e}) \ge q$를 결정하는 알고리즘이 존재하는가?

이 문제는 근사치 (approximation) 나 유한 시간 (finite-horizon) 문제가 아니라, 무한 시간 (infinite-horizon) 에 대한 정확한 값을 다루는 데 중점을 둡니다.

2. 방법론 (Methodology)

저자는 다음과 같은 단계들을 통해 문제를 분석하고 증명했습니다.

A. 구조적 장벽: 유한 시간과 무한 시간의 불일치

• 지연 활성화 (Delayed-activation) 채널 패밀리 구축:
  • 저자는 $N$단계 동안은 출력이 항상 0 이고 (정보 전달 없음), $N+1$단계 이후에만 채널이 활성화되어 정보를 전달하거나 잡음을 발생시키는 두 가지 채널 ($Ch_{good}$, $Ch_{bad}$) 을 구성했습니다.
  • 두 채널은 $N+1$ 단계까지의 모든 유한 시간 구간에서 동일한 동작을 보입니다 (지시 정보 Directed Information 이 0).
  • 그러나 $N \to \infty$일 때의 정확한 피드백 용량은 다릅니다:
    • $Ch_{good}$: 무잡음 상태가 되어 용량이 1 로 수렴.
    • $Ch_{bad}$: 완전한 잡음 상태가 되어 용량이 0 으로 수렴.
• 결론: 어떤 고정된 유한 시간 $N$에서도 채널의 초기 행동을 관찰한다고 해서 무한 시간의 정확한 용량을 결정할 수 없습니다. 이는 **균일한 유한 시간 특성화 (Uniform Finite-Horizon Characterization)**가 불가능함을 의미합니다.

B. 계산 이론적 증명 (불가결성 증명)

• 환원 (Reduction): 알려진 결정 불가능 문제 (예: 정지 문제 또는 특정 언어의 멤버십 문제) 를 위에서 정의한 채널 임계값 문제로 환원시켰습니다.
• 증명: 만약 피드백 용량 임계값을 결정하는 알고리즘이 존재한다면, 환원된 결정 불가능 문제도 해결할 수 있어야 하므로 모순이 발생합니다.
• 결과: 이진 입력/출력, 유리수 파라미터, 단일 사역 (unifilar) 특성을 가진 매우 제한된 클래스의 FSC 에 대해서조차 **정확한 피드백 용량 임계값 결정 문제는 불가결 (Undecidable)**합니다.

C. 대수적 및 논리적 함의

• $\exists \mathbb{R}$ (실수의 존재 이론) 비포함:
  • 많은 기하학적/대수적 결정 문제들은 실수의 존재 이론 ($\exists \mathbb{R}$) 에 속하며 PSPACE 에 포함됩니다.
  • 그러나 이 논문의 임계값 언어 $L_{Cap}$는 $\exists \mathbb{R}$에 속하지 않습니다. 만약 속한다면 결정 가능해야 하는데, 앞서 증명된 불가결성과 모순되기 때문입니다. 즉, 이 문제는 다항식 방정식/부등식 시스템으로 환원될 수 없습니다.
• Gödel-Tarski-Löb (GTL) 결과:
  • 이 불가결성은 형식적 이론 (Recursively Axiomatizable Theories) 에 대한 메타-수학적 결과를 도출합니다.
  • Gödel: 정확한 피드백 용량 명제에 대한 완전한 공리계는 존재할 수 없습니다 (불완전성).
  • Tarski: 해당 이론 내에서 용량의 진리 (Truth) 를 정의하는 술어는 존재할 수 없습니다.
  • Löb: 이론이 자신의 증명에 대한 반사 원리 (Reflection Principle) 를 일관되게 증명할 수 없습니다.

3. 주요 기여 (Key Contributions)

1. 정확한 피드백 용량 결정 문제의 불가결성 증명:
   • 기존에 구조화된 FSC 하위 클래스 (예: 특정 메모리 구조) 에서는 계산 가능한 용량 공식이 존재했으나, 저자는 유리수 단일 사역 FSC라는 비교적 자연스럽고 구체적인 클래스에서도 정확한 임계값 결정이 불가능함을 보였습니다.
2. 실수 대수적 프레임워크의 한계 규명:
   • 피드백 용량 문제가 $\exists \mathbb{R}$ (Existential Theory of the Reals) 범위를 벗어남을 증명하여, 다항식 시스템 기반의 보편적 해법이 불가능함을 보였습니다.
3. 정보이론과 논리학의 연결:
   • Shannon 의 정보 이론적 개념 (피드백 용량) 을 Gödel, Tarski, Löb 의 논리학적 불완전성 및 정의 불가능성 정리와 직접적으로 연결했습니다. 이는 정보 이론적 명제에 대한 형식적 증명 시스템의 근본적 한계를 보여줍니다.
4. 구조적 장벽 제시:
   • 유한 시간 (Finite-horizon) 최적화 값들이 수렴하더라도, 무한 시간의 정확한 용량을 결정하는 데 필수적인 정보가 손실될 수 있음을 구조적으로 증명했습니다.

4. 결과 및 의의 (Results and Significance)

• 근본적 한계: 피드백이 있는 메모리 채널의 정확한 용량을 계산하거나 결정하는 보편적인 알고리즘은 존재하지 않습니다.
• 해석의 중요성:
  • 이 결과는 **근사 알고리즘 (Approximation schemes)**이나 특정 구조를 가진 하위 클래스에 대한 기존 긍정적 결과들을 부정하는 것이 아닙니다.
  • 오히려, 왜 성공적인 FSC 피드백 용량 이론이 항상 **구조적 가정 (Structural Assumptions)**에 의존해야 하는지, 그리고 근사적 접근이 필수적인지에 대한 근본적인 이유를 제공합니다.
• 미래 연구 방향:
  • 결정 가능한 (Decidable) 하위 클래스를 찾는 것 (예: 수렴성, 혼합성 조건이 강한 경우).
  • 허용 오차 (Approximation gap) 가 있는 문제의 결정 가능성 연구.
  • 정확한 용량에 대한 형식적 증명 시스템의 한계를 인정하고, 제한된 범위 내에서 완전한 공리계를 구축하는 연구.

5. 결론

이 논문은 Shannon 의 피드백 용량 개념이 계산 이론과 논리학의 깊은 경계선 위에 있음을 보여줍니다. "정확한 값"을 구하는 문제는 계산적으로 불가능할 수 있으며, 이는 정보 이론의 발전 방향이 보편적인 정확한 해법이 아닌 구조화된 하위 클래스에 대한 정확한 해법과 근사적 해법에 초점을 맞춰야 함을 시사합니다. 저자는 이를 "Shannon 이 Gödel-Tarski-Löb 을 만났다"고 표현하며, 정보 이론의 한계가 수학적 논리의 한계와 맞닿아 있음을 강조합니다.