🔢 mathematics

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

本論文は、有限状態チャネルにおけるフィードバック容量の閾値判定問題が、有理数パラメータを持つユニファリルチャネルの極めて制限されたクラスであっても決定不能であることを証明し、その結果として実数上の多項式系への普遍還元が不可能であり、また十分な表現力を持つ形式的理論においてゲーデル・タルスキー・ロブの不完全性現象が生じることを示しています。

原著者： Angshul Majumdar

公開日 2026-03-19

📖 1 分で読めます🧠 じっくり読む

CC BY 4.0

原著者： Angshul Majumdar

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

この論文は、通信の「限界」について、少し意外な角度から探求した非常に興味深い研究です。専門用語を排し、日常の例え話を使って、何が書かれているのかをわかりやすく解説します。

📡 論文のタイトル：「シャノン、ゲーデル、タルスキー、ロブが出会う：有限状態チャネルのフィードバック容量の『決定不能性』」

一言で言うと：
「通信回線の『最大通信速度（容量）』を、正確に計算して『この速度以上か？』と答えられる万能なプログラムは、原理的に存在しない」という結論を導き出した論文です。

🧩 1. 背景：通信の「迷路」と「地図」

まず、通信の世界には「チャネル（通信路）」というものがあって、そこをデータが通ります。

単純な場合（昔の電話など）： 通信路が単純で、過去の履歴に関係ない場合は、最大通信速度を計算する「地図（公式）」がすでに存在しています。
複雑な場合（今回のテーマ）： 通信路に「記憶（履歴）」があり、かつ送信側が「受信側の反応（フィードバック）」を見て送信方法を変えられる場合、計算は非常に複雑になります。

研究者たちは長い間、「この複雑な迷路の出口（最大速度）を、どんな場合でも正確に計算できる万能な地図は作れるだろうか？」と考えてきました。

🕵️‍♂️ 2. この論文の発見：「正解は存在するが、見つけることは不可能」

この論文の著者（アンシュル・マジュンダール氏）は、ある非常に制限された、しかし現実的な通信モデル（「有限状態チャネル」と呼ばれるもの）を使って、以下の衝撃的な結論を出しました。

「『この通信路の最大速度は、100Mbps 以上か？』という質問に、
どんな場合でも正解を出すプログラム（アルゴリズム）は、
数学的に『存在しない』ことが証明された。」

🎭 例え話：「遅延する自動販売機」

論文では、ある特殊な「自動販売機」のような通信路を想像してください。

最初の 100 回： この機械は、どんなボタンを押しても「0」という結果しか出さない（無音の状態）。
101 回目以降： 突然、機械の内部状態が変わり、ボタンを押した通りに正しく反応するようになる。

悪い機械： 101 回目以降も、ボタンと関係なくランダムに「0」か「1」を出す（通信速度は 0）。
良い機械： 101 回目以降は、ボタン通りに正しく反応する（通信速度は最大）。

ここがポイントです！
最初の 100 回（あるいは 1000 回、100 万回）の観察だけでは、「良い機械」か「悪い機械」か、絶対に区別できません。両方とも最初のうちは同じように振る舞うからです。

もし「100 回観察すれば答えが出る」というルールを作ろうとしても、1001 回目で変わる機械を作れば、そのルールは破綻します。
「いつまで観察すればいいか」が、機械によって無限に変わってしまうため、「いつか必ず答えを出す」というプログラムは作れないのです。

🚧 3. なぜこれが重要なのか？（3 つの壁）

この発見は、単に「計算が難しい」という話ではなく、もっと根本的な「壁」を示しています。

壁①：「計算不可能」の壁

「万能な計算機（チューリングマシン）」を使って、この通信速度の正解を導き出すことは、数学的に不可能です。これは、コンピュータの限界を示す「決定不能性（Undecidability）」と呼ばれる概念です。

壁②：「代数方程式」の壁

「多項式（x² + 2x + 1 のような式）」を使って答えを出そうとしてもダメです。この問題は、通常の数学の方程式で解ける範囲（実数の存在理論）を超えており、もっと複雑な「論理の闇」に落ちています。

壁③：「証明の限界」の壁（ゲーデル・タルスキー・ロブ）

ここが最も哲学的で面白い部分です。
「この通信速度が 100Mbps 以上である」という事実を、どんなに優れた「数学の教科書（公理系）」に載せようとしても、その教科書自体が「正しいかどうかを証明できない」場合があることが示されました。

ゲーデルの不完全性定理： 真実であっても、証明できない命題が存在する。
この論文の結論： 通信の「真実」も例外ではない。

💡 4. 悲観的な話ではない！（重要な注意点）

「じゃあ、通信技術はもうダメなのか？」というと、全く違います。

近似は可能： 「100Mbps 以上か？」という正確な答えは出せないかもしれませんが、「99.9% 近い速度」や「100Mbps 以上かどうかの推定」は可能です。実際のエンジニアリングでは、この「近似」で十分です。
特殊なケースは解ける： 非常に単純な通信路や、特定の構造を持った通信路については、まだ計算方法があります。
意味： この論文は、「万能な魔法の杖は存在しない」ということを教えてくれました。だからといって、魔法を使わずに、一つ一つ丁寧に構造を分析して解くという、これまでの素晴らしい研究の成果が否定されるわけではありません。

🌟 まとめ

この論文は、**「通信の『完全な正解』を、どんな場合でも自動的に見つける『万能な機械』は、宇宙の法則（数学）によって禁止されている」**と宣言したものです。

それは、私たちに「完璧な答え」を諦めさせ、代わりに「より良い近似」や「特定の構造に特化した解き方」を探すという、現実的で賢いアプローチの重要性を再確認させてくれる、非常に示唆に富んだ研究です。

「完璧な地図は描けないが、道は開ける」
それがこの論文が伝えるメッセージです。

論文要約：シャノン・ゴードル・タルスキー・ロブとの出逢い：有限状態チャネルにおけるフィードバック容量の決定不可能性

著者: Angshul Majumdar (Indraprastha Institute of Information Technology, Delhi)
日付: 2026 年 3 月 19 日 (ドラフト)

1. 概要と背景

本論文は、記憶を持つ通信チャネル（有限状態チャネル：FSC）におけるフィードバック容量の「厳密な決定問題」を対象としています。シャノンの情報理論において、メモリーレスなチャネルの容量は明確に定義され計算可能ですが、メモリーを持つチャネルやフィードバックが存在する場合には、最適化が履歴に依存し、漸近的な性質を持つため、解析が極めて困難になります。

従来の研究では、特定の構造的制約を持つ部分クラス（例：ユニファリチャネルなど）に対して、動的計画法や構造論的アプローチによる厳密な解や計算可能な上限が得られてきました。しかし、**「一般的な有限状態チャネルのクラスにおいて、フィードバック容量が特定の有理数閾値以上かどうかを判定するアルゴリズムは存在するか？」**という根本的な問いに対して、本論文は否定的な回答（決定不可能性）を示しています。

2. 問題設定

論文が扱う核心的な決定問題は以下の通りです。

入力:
- 2 値入力・2 値出力の有理数パラメータを持つユニファリ有限状態チャネル（Rational Unifilar FSC） $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$ が真か偽か。

ここで注目すべきは、「近似」や「有限時間ホライズン」ではなく、**「厳密な無限時間ホライズン」**の容量に対する判定である点です。

3. 主要な手法と構成

3.1 構造的障壁の構築（遅延活性化ユニファリ族）

決定不可能性の証明のため、著者は「遅延活性化（Delayed-activation）」と呼ばれるユニファリ FSC の族を構築しました。

構造: チャネルは $N$ ステージにわたって出力が常に 0 になる「遅延フェーズ」を持ち、その後に「活性状態」 $\star$ に遷移します。
2 種類のチャネル:
1. Good チャネル: 活性状態以降、入力と出力が完全に一致する（ノイズなし）。
2. Bad チャネル: 活性状態以降、出力が入力に依存しない完全なノイズ（ランダム）。
特徴:
- 任意の有限時間 $n \le N+1$ において、両者のチャネルは全く同じ振る舞い（出力が常に 0、 directed information が 0）を示します。
- しかし、無限時間ホライズンにおける容量は異なります：
  - $C_{fb}(\text{Good}) = 1$
  - $C_{fb}(\text{Bad}) = 0$

この構成により、「有限時間の観測値（有限ホライズンの directed information）が一致しても、無限時間の容量は一致しない」ことが示されました。

3.2 計算複雑性理論への帰着

上記の構成を用いて、既知の決定不可能問題（停止性問題など）から、フィードバック容量の閾値判定問題への多対一帰着（many-one reduction）を構築しました。

任意の決定不可能な問題のインスタンス $i$ に対して、対応するチャネル $e(i)$ と閾値 $q(i)$ を計算可能に生成します。
$i$ が「YES」であることと、 $C_{fb}(e(i)) \ge q(i)$ であることが同値になるように設計します。
もし容量閾値判定アルゴリズムが存在すれば、元の決定不可能問題も解決できてしまうため、矛盾が生じます。

4. 主要な結果と貢献

4.1 決定不可能性の証明（定理 IV.4）

結果: 2 値入力・2 値出力・有理数パラメータ・ユニファリという極めて厳格に制限されたクラスであっても、フィードバック容量の厳密な閾値判定問題は決定不可能です。

意味: 有限状態、有理数係数、決定論的な状態遷移（ユニファリ）といった「良い性質」さえあれば、厳密な容量計算は一般に不可能であることを示しました。

4.2 実数存在理論（ $\exists\mathbb{R}$ ）からの除外（定理 V.7）

結果: 厳密な閾値言語 $L_{Cap}$ は、実数の存在理論（Existential Theory of the Reals, $\exists\mathbb{R}$ ）に属しません。

背景: 多くの幾何学的・代数的決定問題は $\exists\mathbb{R}$ に属し、PSPACE 内で決定可能です。
意義: フィードバック容量の厳密な判定は、多項式時間多対一帰着によって実数の多項式不等式系に還元できないことを意味します。これは、従来の代数的アプローチではこの問題の厳密解を得られないことを示唆しています。

4.3 有限ホライズン表現の不可能性（相関 IV.7）

結果: 任意の固定された有限時間 $N$ に対して、 $V_1, \dots, V_N$ （有限時間 directed information の最適値）の値のみからフィードバック容量を一意に決定する関数は存在しません。

意義: 有限時間での振る舞いだけでは、漸近的な容量を特定できないという構造的な障壁を証明しました。

4.4 論理的帰結：ゴードル・タルスキー・ロブの不完全性定理（セクション VI）

決定不可能性をメタ理論的に解釈し、情報理論的述語を記述する形式体系における限界を導きました。

ゴードルの不完全性定理: 再帰的に公理化された健全な理論 $T$ は、すべての容量閾値命題 $Cap(e, q)$ を決定できません（完全ではありません）。
タルスキーの真理定義不可能性: そのような理論 $T$ 内部で、容量の真偽を定義する述語（真理述語）を構成することはできません。
ロブの定理: 理論 $T$ が「自分自身で証明した容量閾値命題は真である」という一様反射原理を証明することは不可能です。

5. 意義と結論

5.1 研究への示唆

本論文は、FSC フィードバック容量の研究全体を否定するものではなく、**「厳密な普遍解の限界」**を明確に定義する境界定理（Boundary Theorem）です。

構造的アプローチの重要性: 特定の構造（例：収束性、混合性、特定のグラフ構造）を持つ部分クラスでは、依然として厳密解や計算可能アルゴリズムが存在し得ます。
近似手法の必要性: 厳密な無限時間ホライズンの判定が不可能である以上、実用的なアプローチとしては、近似アルゴリズム、有限時間ホライズンの surrogate、あるいは追加の仮定に基づく部分クラスへの限定が不可欠であることが示されました。

5.2 結論

シャノン、ゴードル、タルスキー、ロブの概念を結びつけ、情報理論の基礎的な量である「フィードバック容量」の厳密な決定問題が、計算可能性理論の観点から本質的に不可能であることを証明しました。これは、情報理論における「計算可能性の壁」を示す重要な成果であり、今後の研究が「どのような構造的条件の下で計算可能性が回復するか」を追求する方向性を指し示しています。