🔢 mathematics

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

この論文は、整数集合の加法系が整数全体を一意に表すかどうかという問題が、コラッツ予想や万能停止問題と同等であり、したがって決定不可能であることを示しています。

原著者： Andrei Zabolotskii

公開日 2026-04-01

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

原著者： Andrei Zabolotskii

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

1. 物語の舞台：「整数の箱詰め」

まず、**「整数（Z）」**とは、$... -2, -1, 0, 1, 2, ...$ という無限に続く数の列です。

著者は、この無限の列を、いくつかの**「箱（集合）」に分けて、「どの箱から 1 つずつ数字を取り出して足し合わせると、どんな整数も 1 通りだけの組み合わせで作れるか？」**という問題を考えました。

例え話：
- 私たちが普段使っている**「10 進法」**は、この「箱」の一種です。
- 箱 1: 0〜9 の数字
- 箱 2: 0, 10, 20, ... 90 の数字
- 箱 3: 0, 100, 200, ... 900 の数字
- これらを組み合わせて「538」を作ると、500 + 30 + 8 となり、これ以外の組み合わせでは作れません。これが「正の整数（0 以上の数）」では完璧に決まっているルールです（これを「ド・ブルーインの定理」と呼びます）。

2. 問題は「負の数」が入ると難解になる

しかし、**「負の数（マイナス）」も含まれると、状況が一変します。
「正の数」のルールを無理やり「負の数」の世界に拡張しようとすると、「本当にすべての整数が作れるのか？」「重複なく作れるのか？」**を確認するのが、非常に難しくなります。

著者は、この問題を**「動的システム（ダイナミカルシステム）」という、「ボールを転がしてどこに落ちるかを見るゲーム」**の視点から捉え直しました。

新しい視点：
- 整数を「箱」に分解する作業は、**「数字をルールに従って変形させ、最終的に『0』にたどり着くかどうか」**というゲームと同じです。
- もし、どんな数字から始めても、このゲームを繰り返せば必ず「0」に落ち着くなら、その箱のセットは「完璧な整数の箱詰め（完全な加法的システム）」と言えます。
- もし、ある数字から始めると、0 にたどり着かず、永遠にループしたり、無限に大きくなったりするなら、その箱のセットは「不完全」です。

3. 驚きの発見：「未解決問題」へのリンク

ここで、この論文の最も劇的な部分が登場します。著者は、この「箱詰めが完璧かどうか」を判定する問題が、**「数学界の伝説的な難問」と「コンピュータの計算不可能性」**に直結していることを証明しました。

A. コラッツ予想とのリンク

**「コラッツ予想」**とは、こんなゲームです。

数字が偶数なら「半分にする」
数字が奇数なら「3 倍して 1 を足す」
これを繰り返すと、どんな数字から始めても必ず「1」にたどり着くのか？（※まだ証明されていません）

著者は、「ある特定の箱のセットが、すべての整数を完璧にカバーしているかどうか」を判定することは、実は「コラッツ予想が正しいかどうか」と全く同じ難しさであることを示しました。
つまり、コラッツ予想が解けない限り、その箱のセットが完璧かどうかを数学的に証明することもできません。

B. コンピュータの「停止問題」とのリンク

さらに、**「Fractran（フラクトラン）」**という、分数を使った奇妙なプログラミング言語を使いました。

Fractran の停止問題：「あるプログラムが、どんな入力を与えても、いつか必ず止まる（計算が終わる）のか？」を判定できるか？
これはコンピュータサイエンスの**「決定不能（アルゴリズムで解けない）」**な問題として有名です。

著者は、**「Fractran のプログラムに対応する箱のセットが、すべての整数を完璧にカバーしているかどうか」を判定する問題は、この「停止問題」と同じくらい難しい（解けない）**ことを証明しました。

4. 結論：何が起きたのか？

この論文は、以下のようなメッセージを伝えています。

数学の壁： 「整数を箱にきれいに分ける」という一見単純な問題が、実は**「数学的に解けない問題（決定不能）」**の入り口になっている。
意外なつながり： 「整数の足し算」という純粋な数学の問題と、「コラッツ予想」や「コンピュータが止まるかどうか」という全く別の分野の問題が、同じ深さの難しさで繋がっている。
未来への示唆： 私たちが「この箱のセットは完璧か？」と聞かれても、答えを出すための「万能な計算機（アルゴリズム）」は存在しない可能性があります。それは、神様（あるいは数学の真理）だけが知っている領域だからです。

まとめ

この論文は、**「整数を箱に詰めるゲーム」を通じて、「数学には、どんなに頑張っても人間やコンピュータが『正解』を導き出せない壁がある」**ことを、驚くべき形で示した作品です。

まるで、**「このパズルが完成しているか確認するには、宇宙の歴史が終わるまで計算し続ける必要があるかもしれない」**と言われているような、不思議で壮大な世界観を持っています。

以下は、Andrei Zabolotskii による論文「Additive systems for Z are undecidable（整数の加法系は決定不可能である）」の技術的な詳細な要約です。

1. 研究の背景と問題設定

問題の定義:
本論文は、整数集合 $\mathbb{Z}$ に対する「加法系（additive system）」の存在と決定可能性を扱っています。
加法系とは、集合の列 $A = \{A_0, A_1, \dots\}$ （各 $A_i \subset \mathbb{Z}$ ）であり、任意の整数 $n \in \mathbb{Z}$ が、 $n = a_0 + a_1 + \dots$ （ただし $a_i \in A_i$ 、かつ有限個を除き $a_i=0$ ）という形で一意に表現できるような系を指します。

既存の知見:

非負整数 $\mathbb{N}_0$ の場合: de Bruijn の定理により、 $\mathbb{N}_0$ 上の加法系は完全に特徴付けられています。これらは「イギリス式数体系（British number systems）」と呼ばれる特定の構造（可変基数の位値記数法）の縮約（contraction）として記述されます。
整数 $\mathbb{Z}$ の場合: $\mathbb{Z}$ に対する加法系の問題は非常に困難であり、完全な解決策は知られていません。既存の研究は主に 2 つの集合による分解（ $Z = A \oplus B$ ）に焦点が当てられており、無限の集合列を持つ一般的なケースについては未解決でした。

核心的な問い:
「与えられた特定の構造を持つ集合の列（加法系の候補）が、実際に $\mathbb{Z}$ の加法系（完全な加法系）であるかどうかを、アルゴリズム的に判定できるか？」

2. 手法とアプローチ

著者は、加法組合せ論の視点を**力学系（dynamical systems）**の視点へと転換することで、この問題を解決しました。

主要な概念の導入:

標準的コレクション（Canonical Collections）:
- $\mathbb{N}_0$ の数体系を自然に一般化し、 $\mathbb{Z}$ における基本的な例（負二進法、平衡三進法など）を包含する集合の列を定義しました。
- 基底の列 $(b_i)$ と、各 $b_i$ に関する完全剰余系 $(T_i)$ （0 を含む）によって定義されます。集合 $A_i$ は $b_0 b_1 \dots b_{i-1} T_i$ の形をとります。
- この構造において、任意の整数 $n$ の展開（表現）は、一意に決定されます。問題は、その展開が「有限項で 0 に収束するか（つまり $n$ が和集合に含まれるか）」に帰着されます。
標準系（Canonical Systems）への翻訳:
- 集合の列を、整数上の写像の列（力学系）として再解釈しました。
- 整数 $n$ に対して、 $n$ を $b_i$ で割った余り $t_i(n) \in T_i$ を取り除き、商を次の状態とする写像 $f_i$ を定義します。
- $f_i(n) = \frac{1}{b_i}(n - t_i(n))$
- 命題 1: 標準的コレクションが完全（ $\mathbb{Z}$ の加法系）であるための必要十分条件は、任意の整数 $n$ に対する軌道（trajectory）が、有限ステップ後に恒等的に 0 になることです。

3. 主要な結果

著者は、標準的コレクションの完全性の判定問題が、数学の有名な未解決問題や決定不可能問題と等価であることを証明しました。

定理 1: コラッツ予想との等価性

主張: ある標準的コレクション $A_C$ が存在し、 $A_C$ が完全であることと、コラッツ予想（Collatz conjecture）が真であることは同値です。
構成: コラッツ写像 $f_C(n)$ （奇数なら $3n+1$ 、偶数なら $n/2$ ）を標準系の写像 $f_i$ に埋め込むように基底 $b_i$ と剰余系 $T_i$ を設計しました。
意味: コラッツ予想が真であれば、この特定の標準的コレクションは $\mathbb{Z}$ の加法系となります。逆に、このコレクションが加法系かどうかを判定するアルゴリズムがあれば、コラッツ予想を解決できることになります。

定理 2: Fractran による普遍半停止問題との等価性

主張: Conway が考案した esoteric プログラミング言語「Fractran」を用いて、より強力な結果を示しました。
- Fractran プログラム $F$ に対して、対応する「Fractran 型標準的コレクション」 $A_F$ を構成します。
- $A_F$ が完全であること $\iff$ プログラム $F$ がすべての入力に対して停止する（universal halting）
帰結（Corollary 2）:
- Fractran プログラムがすべての入力で停止するかどうかを判定する問題は**決定不可能（undecidable）**です（チューリング完全性による）。
- したがって、**「与えられた Fractran 型標準的コレクションが完全かどうかを判定する問題は決定不可能である」**ことが導かれます。
- これは、非常に「良く振る舞う（well-behaved）」有限データで定義される集合の列であっても、それが加法系かどうかを一般的に決定するアルゴリズムは存在しないことを意味します。

4. 貢献と意義

決定不可能性の確立:
整数 $\mathbb{Z}$ 上の加法系の完全性判定問題が、計算理論における「決定不可能」な問題に帰着されることを初めて示しました。これは、 $\mathbb{N}_0$ における de Bruijn の定理による完全な特徴付けとは対照的な、 $\mathbb{Z}$ の構造の複雑さを浮き彫りにしています。
分野間の架け橋:
加法組合せ論（数論的構造）と、力学系、計算理論（決定不可能性）、そして未解決問題（コラッツ予想）を直接結びつけました。特に、Fractran という特殊な言語を用いて、数論的な構造の性質をプログラムの停止性に変換する巧妙な構成は画期的です。
標準的コレクションの理論的枠組み:
$\mathbb{Z}$ 上の加法系を研究するための新しい枠組み「標準的コレクション」を提案し、それが数値表現の一般化として機能すること、かつ力学系の軌道として解析可能であることを示しました。
今後の展望:
本研究は、加法系の存在問題が単なる数論的な問いではなく、計算の限界や動的な挙動と深く関連していることを示唆しています。コラッツ予想のような未解決問題が、特定の加法系の完全性として定式化できる点は、これらの問題への新たなアプローチの可能性を開くものです。

まとめ

本論文は、整数 $\mathbb{Z}$ 上の加法系（一意な和分解を持つ集合列）の完全性を判定する問題が、決定不可能であることを証明しました。著者は「標準的コレクション」という新しい概念を導入し、これを力学系の軌道問題として定式化しました。その結果、この判定問題が「コラッツ予想」や「Fractran プログラムの普遍半停止問題」と同値であることを示し、加法組合せ論の重要な未解決問題が計算理論の限界に直結していることを明らかにしました。