A Linear-Size Block-Partition Fibonacci Encoding for Gödel Numbering

以下は、Zoltán Sóstai による論文「A LINEAR-SIZE BLOCK-PARTITION FIBONACCI ENCODING FOR GÖDEL NUMBERING（ゲーデル数化のための線形サイズブロック分割フィボナッチ符号化）」の技術的要約です。

1. 問題背景と目的

ゲーデルの不完全性定理は、形式体系の構文対象（記号、式、証明など）を自然数に符号化する「ゲーデル数化」を必要とします。

• 既存手法の課題:
  • 素数冪法 (Gödel, 1931): 第 $i$ 番目の素数 $p_i$ を用いて $p_1^{a_1+1} \cdots p_m^{a_m+1}$ とする手法。単射性は保証されるが、生成される数が極めて巨大になり、短くても数十〜数百桁のコードとなる。
  • Rosko のペアリング関数 (Rosko, 2025): ゼッケンドルフ表現（非隣接フィボナッチ数の和）に基づく「キャリーレスペアリング」を用いた手法。これを右入れ子（right-nesting）でシーケンス符号化に適用すると、コードの桁数が長さ $m$ に対して指数関数的に増加する（$\Theta(2^m)$）ことが知られていた。
• 本研究の目的:
  • 文字列から自然数への単射的符号化を構築し、符号長の最悪ケースが文字列の長さ $m$ に対して線形（$\Theta(m)$） となることを保証すること。
  • 情報理論的下限に近い効率性を持ちながら、ゼッケンドルフ表現の一意性を活用した新しい構成法を提案すること。

2. 手法：ブロック分割フィボナッチ符号化

本研究は、フィボナッチ数列を「ブロック」に分割し、各文字列の位置に対応するブロックから 1 つのフィボナッチ数を選択する方式を提案しています。

• 基本定義:

  • 文字集合 $\Sigma$ のサイズを $k$ とする。
  • ブロックサイズ $\beta = k + 1$ と定義する。
  • 位置 $i$（0-indexed）に対応するブロック $B_i$ は、フィボナッチ数列のインデックス集合 $\{2 + i\beta, 2 + i\beta + 1, \dots, 2 + i\beta + (k-1)\}$ として定義される。
  • ギャップの確保: 各ブロックの直後（インデックス $2 + i\beta + k$）は使用されない「ギャップ」となる。これにより、隣接するブロック $B_i$ と $B_{i+1}$ から選ばれたインデックスは、フィボナッチ数列上で少なくとも 2 つ離れる（非隣接）ことが保証される。

• 符号化プロセス:

  1. 文字列 $s = s_1 s_2 \dots s_m$ の各位置 $i$ における文字 $s_i$ を、対応する符号 $c_i \in \{0, \dots, k-1\}$ に変換する。
  2. 位置 $i$ に対応するブロック $B_i$ から、インデックス $2 + i\beta + c_i + 1$ のフィボナッチ数 $F_{2 + i\beta + c_i + 1}$ を選択する。
  3. 選択されたすべてのフィボナッチ数の和を計算し、これを符号値 $\lceil s \rceil$ とする。
  4. 空文字列は 0 に符号化される。

• 復号の原理:

  • ゼッケンドルフの定理: 任意の正の整数は、非隣接なフィボナッチ数の和として一意に表現される。
  • 本符号化では、ブロック間のギャップにより「非隣接性」が構造的に保証されているため、符号値（和）からゼッケンドルフ支持（使用されたインデックスの集合）を貪欲法で復元でき、そこから元の文字列の長さと各位置の記号を一意に決定できる。

3. 主要な結果と定理

• 単射性と復号可能性 (Theorem 4.2, 4.5):

  • 異なる文字列は異なる自然数に符号化される（単射）。
  • 符号値から元の文字列を一意に復元可能。
  • 文字列の長さは、符号値のゼッケンドルフ支持に含まれるインデックスの数（または最大インデックス）から直接復元可能。

• 線形な符号長 (Theorem 5.1):

  • 長さ $m$ の文字列に対して、生成される符号の桁数 $L(m)$ は $\Theta(m)$ となる。
  • 具体的には、最大インデックスは約 $m\beta$ であり、フィボナッチ数の対数成長（$\log F_n \approx n \log \phi$）により、桁数は $m$ に比例する。
  • 10 文字アルファベットの場合、文字あたり約 2.3 桁の増加となる。

• 最適性 (Theorem 5.2):

  • 長さ $m$ の文字列は $k^m$ 通り存在するため、情報理論的下限は $m \log_{10} k$ 桁である。
  • 本手法の定数倍オーバーヘッドは $\frac{(k+1)\log_{10}\phi}{\log_{10}k}$ であり、漸近的に最適（線形）であることが示された。

• 既存手法との比較 (Proposition 5.3):

  • Rosko のキャリーレスペアリングを右入れ子形式で用いる場合、最悪ケースで $\Theta(2^m)$ の桁数増加（指数関数的増大）が発生する。
  • 本ブロック分割法はこの指数増大を回避し、線形成長を実現している。

4. 比較表（要約）

5. 意義と貢献

• 理論的貢献: ゼッケンドルフ表現（非隣接フィボナッチ和）をベースにしたゲーデル数化において、初めて線形サイズの符号化を実現した。
• 効率性の向上: 従来のペアリング関数の入れ子構造による指数爆発を回避し、情報理論的下限に近い定数倍で済む実用的な符号化を提供した。
• 将来の展望:
  • この符号化の「加法性」が、有界算術における構文述語の $\Delta_0$ 定義可能性の確立や、乗法を持たない体系における不完全性証明の構築など、理論内部の目的に利用可能かどうかが今後の課題として提起されている。
  • 完全な構文の算術化（代入、連結、対角化など）は本稿では扱っていないが、数値符号化レイヤーとして機能する。

結論

本論文は、フィボナッチ数列をブロック単位に分割し、ブロック間のギャップを利用して非隣接性を保証する単純ながら強力な構成法を提案しました。これにより、ゼッケンドルフ表現の一意性を活かしつつ、符号長が文字列長に対して線形にしか増大しない、効率的かつ理論的に健全なゲーデル数化手法を確立しました。