A Finite-State Proof of the Well-Definedness of a Perturbed Hofstadter Sequence

1. 연구 배경 및 문제 제기 (Problem Statement)

• 배경: 메타 - 피보나치 (Meta-Fibonacci) 재귀 수열은 재귀식의 인자가 이전에 계산된 값에 의존하는 수열입니다. 가장 유명한 예는 Hofstadter 의 Q-수열 ($Q(n) = Q(n-Q(n-1)) + Q(n-Q(n-2))$) 입니다.
• 문제: 이러한 수열의 가장 근본적인 질문 중 하나는 정의 가능성 (Well-definedness) 여부입니다. 즉, 모든 $n \ge 1$에 대해 재귀 호출의 인자 ($n-Q(n-1)$ 등) 가 항상 양수인지, 혹은 수열이 유한한 단계에서 정의되지 않고 멈추지 (undefined) 않는지 확인하는 것입니다.
• 현황: 고전적인 Hofstadter Q-수열의 경우, 이 정의 가능성 여부는 여전히 해결되지 않은 난제 (open problem) 로 남아 있습니다.
• 연구 대상: 본 논문은 고전적인 Q-수열에 교번하는 항 $(-1)^n$을 추가하여 변형된 (Perturbed) Hofstadter-type 수열을 다룹니다.
  • 정의: $Q(1)=1, Q(2)=1$, 그리고 $n \ge 3$에 대해
    $$Q(n) = Q(n - Q(n - 1)) + Q(n - Q(n - 2)) + (-1)^n$$
  • 이 교번 항은 재귀의 전파 행동을 구조적으로 변화시켜, 고전적 경우와 다른 분석적 접근을 가능하게 합니다.

2. 방법론 (Methodology)

논문은 무한한 재귀 구조를 **유한한 조합론적 시스템 (Finite Combinatorial System)**으로 축소하는 유한 상태 (Finite-State) 방법론을 제시합니다. 주요 단계는 다음과 같습니다.

2.1 심볼릭 인코딩 및 문맥 (Contexts)

• $Q(n)$의 실제 수치 값 대신, 재귀의 국소적 행동을 나타내는 유한한 심볼릭 상태 집합 $S = \{S_0, \dots, S_7\}$을 도입합니다.
• 재귀의 교번 항으로 인한 오차를 보정하기 위해 부채 (Debt) 파라미터 $d \in \{0, 2\}$를 추가합니다.
• 문맥 (Context): 재귀의 국소적 구조를 인코딩하는 튜플 $\lambda = (p, R, i, \pi, d)$로 정의됩니다. 여기서 $p$는 패턴, $R$은 재귀 영역, $i$는 위치, $\pi$는 패리티, $d$는 부채입니다.
• 적합한 문맥 집합 ($\Lambda_{adm}$): 재귀 규칙과 일관된 유한한 문맥들의 집합으로, 총 28 개의 원소를 가집니다.

2.2 호환성 그래프 (Compatibility Graph)

• 인접한 위치 간의 재귀 전파를 방향 그래프 $(\Lambda_{adm}, \Psi)$로 모델링합니다.
• $\Psi$는 어떤 문맥 $\lambda$가 다음 문맥 $\mu$를 가질 수 있는지를 결정하는 호환성 관계입니다.
• 이 그래프는 28 개의 정점과 34 개의 간선으로 구성되며, 부채 0 과 부채 2 에 따라 두 개의 연결 성분으로 나뉩니다.

2.3 전역 할당 및 제약 만족 문제 (CSP)

• 수열의 전역적 정의 가능성은 이 유한한 그래프에서 **모든 간선을 만족하는 전역 할당 (Global Assignment)**의 존재 문제로 환원됩니다.
• 정리 2 (유한 상태 축소): 원래 재귀가 모든 $n$에 대해 정의될 필요충분조건은, 해당 유한 제약 시스템에 **방해 요소 (Obstruction)**가 없는 것입니다. 즉, 국소적으로 허용 가능한 모든 부분 할당이 전역적으로 확장 가능한지 확인하는 문제입니다.

2.4 두 가지 모드 구조 (Two-Mode Structure)

• 분석 결과, 모든 유효한 할당은 두 가지 전역 모드 (Mode A 와 Mode B) 중 하나에 속함이 증명됩니다.
  • Mode A: 기준 문맥 $\lambda_0$에서 상태 $S_1[0]$을 가짐.
  • Mode B: 기준 문맥 $\lambda_0$에서 상태 $S_2[0]$을 가짐.
• 이 이분법적 구조는 전역 확장을 두 가지 경우로만 나누어 분석할 수 있게 합니다.

2.5 임계 코어 (Critical Core) 로의 축소

• 방해 요소가 존재한다면, 그것은 반드시 **민감한 문맥 (Sensitive Contexts, $\Lambda_{sens}$)**의 부분집합에 존재해야 함을 증명합니다.
• 더 나아가, 모든 최소 방해 요소는 임계 코어 (Critical Core) $\Lambda_{crit} = \{\lambda_0, \lambda_2, \lambda_{14}, \lambda_{24}\}$라는 4 개의 문맥으로 축소됨을 보입니다.
• 이는 무한한 재귀의 정의 가능성 문제를 4 개의 문맥으로 이루어진 15 개의 비어 있지 않은 부분집합에 대한 유한한 검증 문제로 만듭니다.

3. 주요 결과 (Key Results)

1. 주요 정리 (Theorem 1): 변형된 Hofstadter 수열 $Q(n) = Q(n - Q(n - 1)) + Q(n - Q(n - 2)) + (-1)^n$은 모든 $n \ge 1$에 대해 **잘 정의됨 (Well-defined)**이 증명되었습니다. 즉, 모든 재귀 인자는 양수를 유지합니다.
2. 방해 요소의 부재: 임계 코어 $\Lambda_{crit}$의 모든 부분집합에 대해 유효한 할당이 존재함이 **완전한 유한 검증 (Exhaustive Finite Verification)**을 통해 확인되었습니다.
   • 특히, Mode A에서 모든 문맥에 대해 일관된 상태 $S_1[0]$을 할당하는 **균일 할당 (Uniform Assignment)**이 모든 호환성 제약을 만족함을 발견했습니다.
   • 이는 수열의 정의 가능성에 대한 구조적 안정성을 보여줍니다.
3. 컴퓨팅 검증: 모든 계산은 공개된 저장소 [15] 에 있는 머신 체크 가능한 코드로 구현되었으며, 부록 A 에는 15 가지 부분집합에 대한 검증 결과가 명시적으로 제시되어 있습니다.

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

• 첫 번째 엄밀한 증명: 고전적인 Hofstadter Q-수열의 정의 가능성은 미해결 상태인 반면, 본 논문은 교번 항이 포함된 변형 모델에 대해 첫 번째 완전한 증명을 제시합니다.
• 새로운 방법론의 제시: 비국소적 (Non-local) 인자를 가진 메타 - 피보나치 재귀를 유한 상태 기계 (Finite-State Machine) 및 **제약 만족 문제 (CSP)**로 축소하는 강력한 방법론을 제시했습니다. 이는 무한한 재귀를 유한한 조합론적 구조로 변환하여 분석할 수 있음을 보여줍니다.
• 구조적 통찰: 교번 항 $(-1)^n$이 단순한 섭동이 아니라, 재귀의 전파 행동을 근본적으로 변화시켜 유한 상태 축소를 가능하게 하는 구조적 비대칭성을 생성함을 밝혔습니다.
• 확장 가능성: 이 방법은 다른 제한된 섭동을 가진 메타 - 피보나치 재귀에 대한 정의 가능성 증명을 위한 일반적인 프레임워크로 활용될 수 있음을 시사합니다.

5. 결론

이 논문은 변형된 Hofstadter 수열이 모든 $n$에 대해 잘 정의됨을 증명하기 위해, 무한한 재귀를 유한한 심볼릭 시스템과 호환성 그래프로 축소하고, 이를 두 가지 전역 모드로 분류한 후, 4 개의 핵심 문맥으로 이루어진 '임계 코어'에서의 방해 요소 부재를 컴퓨터를 통한 완전 검증을 통해 확인했습니다. 이는 비국소적 재귀 수열의 분석에 있어 유한 상태 방법론의 유효성을 입증한 중요한 성과입니다.