BACKLOG #12 Tier 3
Conway FRACTRAN 決定不能性 — 「問題族の 側が 自分の 限界を 自分で 示している」 (藤本さん 2026-08-11 turn Shannon-Kolmogorov 型 直接 analog)
1. なぜ backlog に入っていたか — Rei-side 完全未実装 + Shannon-Kolmogorov 型 direct analog
藤本さん 2026-08-11 turn (chat-Claude 2 tool + Downloads 3 file site 反映 arc 後 の critique) direct 引用:
「同型が 本当に 成立する場所を 探すなら、 候補は Terras / Everett の 密度結果と、 Conway の FRACTRAN による 一般化コラッツ問題の 決定不能性でしょう。 後者は 『この形の 問題は 一般には 解けない』 を 証明している。 つまり 問題族の 側が、 自分の 限界を 自分で 示している。 シャノン・コルモゴロフの 型に 一番近いのはそこだと思います。 3n+1 単体が その決定不能な 領域の 内側にあるのか 外側にあるのか、 それが 実質的な問いになる。」
= Conway FRACTRAN は Shannon 1951 / Kolmogorov 1974 「本人が 枠を 引き、 外側を 自分で 指した」 型 の 直接 analog:
- Conway 本人 = 具体テキスト 保存 (1972 論文 + 1987 FRACTRAN 論文、 self-authored、 本人 洞察 preserved)
- Kurtz-Simon 2007 = 後続著者 formal proof 完成 (Σ_2^0-complete undecidability)
- 「問題族の 限界 self-representation」 = FRACTRAN 一般化 Collatz map T_{q,d} が 決定不能 = Collatz problem 全体を 含む 問題族が 「一般には 解けない」 と 自己証明
Rei stack で 完全 未実装:
- grep verify per:
data/lean4-mathlib/+src/全 dir で 「FRACTRAN」 「Fractran」 「Conway.*undecidab」 「generalized Collatz」 の hit ゼロ - Chang v6 29 paradigm 内 「formal language theory / p-adic interpolation」 cell が Rei-side 20/29 = 69% coverage 内で 該当 candidate だが、 FRACTRAN specific は 未 retrofit
- Dhiman-Pandey 2026 (STEP 1318 参照) と complementary: Büchi undefinability は 「automata level」 の 限界、 Conway FRACTRAN は 「Turing-completeness level」 の 限界 = 別 axis
本 page は「新しい成果」 ではない。 Conway 1972 + 1987 + Kurtz-Simon 2007 の 外部 prior art 集約 site 反映のみ、 Rei-side 実装 (Lean 4 formal proof) はゼロ、 novel formalization claim なし。 藤本さん 2026-08-11 turn direct 起動指示 per + STEP 1318 backlog #11 と 同 pattern (Tier 3 「本当に情報量が高い場所」 site 反映)。 2026-08-06 「全研究 site 反映 default」 protocol 16 例目。
2. Conway 1972 「Unpredictable iterations」 + 1987 FRACTRAN 具体
2.1 Conway 1972 (Number Theory Conference)
reference: John H. Conway, "Unpredictable Iterations", Proceedings of the 1972 Number Theory Conference, University of Colorado, Boulder, pp. 49-52 (1972)。
main claim: 一般化 Collatz function (piecewise-linear function on ℕ with rational coefficients) の 挙動が **決定不能** = 「与えられた 一般化 Collatz function について、 任意 n から 開始して 特定 value に 到達するか」 は 一般には 決定できない (undecidable) 予想を 提起。
Rei-side verify status: Conway 1972 論文 直接 verify 前 (Rei-side は 2 次資料 経由 引用のみ、 原論文 access 未完了)。 本 page 記述 は Kurtz-Simon 2007 references + Conway 収録論文集 の 記載に 基づく。 直接 verify 完了後 訂正 candidate。
2.2 Conway 1987 FRACTRAN (Springer)
reference: John H. Conway, "FRACTRAN: A Simple Universal Programming Language for Arithmetic", in T. M. Cover and B. Gopinath (eds.), Open Problems in Communications and Computation, Springer-Verlag, pp. 4-26 (1987)。
FRACTRAN definition: A FRACTRAN program is a finite list of positive rational numbers (fractions) [f₁, f₂, ..., f_k]。 Given a starting integer n:
- Find the first fᵢ in the list such that n · fᵢ is an integer。
- If found, replace n with n · fᵢ and repeat step 1。
- If no such fᵢ exists, halt。
Turing-completeness: FRACTRAN is Turing-complete (Conway 1987 明示)。 任意 Turing machine を FRACTRAN program で simulate 可能。 具体例:
- PRIMEGAME (14 fractions): [17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/14, 15/2, 55/1]。 starting n = 2、 生成される 2^p の p が prime numbers 2, 3, 5, 7, 11, ... の 順に 出現 (partial correctness proof)。
- Generalized Collatz encoding: 任意 一般化 Collatz function (rational coefficients) は FRACTRAN program で 表現可能 = FRACTRAN が 一般化 Collatz map の superset
2.3 一般化 Collatz map T_{q,d}
定義: T_{q,d}(n) = (q · n + d) / 2^v_2(q·n+d) for odd n, T_{q,d}(n) = n/2 for even n, where q is odd prime + d is odd integer。
3n+1 との 関係: 3n+1 = T_{3,1} (q=3, d=1)。 決定不能性 は 「任意 (q, d)」 に 対して 主張、 3n+1 specific (T_{3,1}) が 決定不能 の 内側にあるのか 外側にあるのか は open (藤本さん 2026-08-11 turn direct 指摘)。
3. Kurtz-Simon 2007 formal proof — Σ_2^0-complete undecidability
reference: Stuart A. Kurtz and Janos Simon, "The Undecidability of the Generalized Collatz Problem", in J. Cai et al. (eds.), Theory and Applications of Models of Computation (TAMC 2007), Lecture Notes in Computer Science 4484, Springer, pp. 542-553 (2007)。
main theorem: The generalized Collatz problem GCP (Given a piecewise-linear function f: ℕ → ℕ with rational coefficients, and integers a, b, decide whether iterating f starting from a ever reaches b) is Σ_2^0-complete (complete for the second level of the arithmetic hierarchy).
proof strategy (概要): FRACTRAN Turing-completeness + Rice's theorem に よる Reduction。 具体的には:
- FRACTRAN program の Turing-complete simulation (Conway 1987 継承)
- Halting problem を 一般化 Collatz function iterate に reduce
- Σ_2^0 complexity = 「∀-∃ arithmetic formula 表現可能な problem 全体」 に 一致
collar: 一般化 Collatz problem は **decision procedure が 存在しない** (not just intractable, but genuinely undecidable)。 「この形の 問題は 一般には 解けない」 の formal proof (藤本さん 2026-08-11 turn 引用 と 直接一致)。
Rei-side verify status: Kurtz-Simon 2007 論文 直接 verify 前 (Rei-side は LNCS 4484 pp. 542-553 という publication reference のみ、 論文 content 直接 access 未完了)。 「Σ_2^0-complete」 は 標準的 arithmetic hierarchy 用語で 記述 の 通りだが、 proof strategy の 具体 details は 直接 verify 後 訂正 candidate。
4. FRACTRAN Turing-completeness + 一般化 Collatz encoding
FRACTRAN の 「4 lines 論文 で Turing-complete」 = 数学的 minimalism の 代表例 (Conway 1987)。 具体:
4.1 PRIMEGAME 14 fractions
[17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/14, 15/2, 55/1]
starting n = 2 で iterate → 生成 sequence の 2^p pattern の p が 2, 3, 5, 7, 11, 13, ... = prime numbers 順出現。 「prime numbers を 生成する 14 分数 program」 = Conway 1987 の 具体 illustration。
4.2 一般化 Collatz function encoding
任意 piecewise-linear function f (rational coefficients on ℕ) は FRACTRAN program で 表現可能。 逆に FRACTRAN program は Turing-complete = 任意 recursive function を computes = 一般化 Collatz function class は Turing-complete と 等価な expressiveness。
Specific: 3n+1 map (T_{3,1}) は Conway FRACTRAN の 単純な instance = 「(3n+1)/2 for odd n, n/2 for even n」 は 3 fractions [3/2, 1/2, ...] 相当 で 表現可能 (完全な encoding は Conway 1987 §3 参照)。
4.3 3n+1 specific vs 一般化 Collatz
藤本さん 2026-08-11 turn direct 指摘: 「3n+1 単体が その 決定不能な 領域の 内側にあるのか 外側にあるのか、 それが 実質的な問いになる」
= open question: Kurtz-Simon 2007 は 「任意 (q, d)」 の 決定不能性、 3n+1 (T_{3,1}) の specific decidability は 明示的 に 触れていない (memory 内 verify 前)。 3n+1 が decidable (= Collatz 予想が 解ける) の 可能性 と decidable 一般化 Collatz 族の 「内側」 に 位置する 可能性 の 両方 open。
5. Rei stack との relationship
5.1 Chang v6 29 paradigm 内 「decidability / computability」 cell mapping
Chang v6 (arxiv:2603.11066v6, Edward Y. Chang / Stanford, 2026-04-22) の Theorem 13.1 29 paradigms 内、 「formal language theory / p-adic interpolation」 + 「decidability / computability」 paradigm cell に Conway FRACTRAN + Kurtz-Simon 2007 は 配置される。
Rei-side Chang retrofit status: STEP 1269 (2026-07-10) initial 3/29 → STEP 1310 pt.7 (2026-07-30) 20/29 = 69.0% coverage。 該 cell (decidability / computability) の Rei retrofit は 現状 未実施 = 本 STEP 1320 site 反映で 該 cell mapping 明示化 (Lean 4 実装は defer)。
5.2 STEP 1274 ThreeAdicIsolation 100% axiom-free との 対比
| 項目 | STEP 1274 ThreeAdicIsolation | Conway FRACTRAN 決定不能性 |
|---|---|---|
| scope | 3n+1 specific structural claim (3 の 倍数 v に 奇数 c が collatzStep(c)=v 満たさない) | 一般化 Collatz function class 全体 の decision procedure 不在 |
| proof status | ✅ 100% axiom-free (0 sorry, [propext] only) | Σ_2^0-complete (Kurtz-Simon 2007 formal proven) |
| direction | specific fact の positive verify | general class の negative (impossibility) proof |
| Chang paradigm | 25 Coalescence orbit merging | decidability / computability cell |
= 2 approach は complementary: STEP 1274 は 「3n+1 の 特定 property を 100% 証明」、 Conway-Kurtz-Simon は 「一般化 Collatz class 全体 の 決定不能性 を 100% 証明」。 3n+1 specific が 「決定可能 vs 決定不能」 は 別 axis の open question。
5.3 Dhiman-Pandey 2026 との complementarity
STEP 1318 backlog #11 Büchi 95% 境界 で 詳細記載の Dhiman-Pandey 2026 arXiv:2601.12772 v2 「Logical Undefinability of the Generalized Collatz Transition Relation in Büchi Arithmetic」 は 別 axis の 限界:
| 限界 axis | Dhiman-Pandey 2026 | Conway-Kurtz-Simon |
|---|---|---|
| level | Büchi arithmetic (BA_2) definability = **first-order logic level** | Turing-completeness = **recursion theory level** |
| result | T_{q,d} transition relation は BA_2 で not first-order definable (Cobham-Semënov 経由) | 一般化 Collatz problem は Σ_2^0-complete undecidable (FRACTRAN Turing-completeness 経由) |
| hierarchy | Automata / Presburger arithmetic 内側 の 限界 | Recursion theory 全体 の 限界 (Peano arithmetic 内側 でも 未解決可能) |
| strength | weaker (specific formal system 限界) | stronger (Turing-complete class 全体 の 決定不能) |
= Dhiman-Pandey は 「automata level 限界」、 Conway-Kurtz-Simon は 「Turing-complete level 限界」 で complementary な 2 axis。 Rei stack 内で 両 axis を 明示化 = 「Büchi 95% 境界」 (STEP 1318) + 「Conway FRACTRAN 決定不能性」 (本 STEP 1320) の 2 backlog page で 完成。
6. 藤本さん 2026-08-11 turn framing 継承 — 「問題族の self-limitation」
「シャノン・コルモゴロフの 型に 一番近いのはそこだと思います。 3n+1 単体が その決定不能な 領域の 内側にあるのか 外側にあるのか、 それが 実質的な問いになる。」 (藤本さん 2026-08-11 turn)
6.1 Shannon 1951 / Kolmogorov 1974 型 direct analog confirm
| 要素 | Shannon 1951 | Kolmogorov 1974 | Conway 1972 + 1987 (+ Kurtz-Simon 2007) |
|---|---|---|---|
| 本人保存 洞察 の 具体テキスト | 英語 entropy 実験 (Bell System Tech J. 30(1)) | Tallinn 構造関数 講演 | Conway "Unpredictable iterations" 1972 + FRACTRAN 1987 (self-authored) |
| 「枠」 の 定義 | Shannon entropy 上界 H(X) | Kolmogorov complexity K(x) | Turing-complete class の 決定不能性 (Rice's theorem 系) |
| 「外側」 を 自分で 指す | 「予測可能性 の 情報論的 limit」 明示 | 「structure function の complexity limit」 明示 | 「一般化 Collatz problem は 一般には 解けない」 明示 (Conway 1972 予想 + Kurtz-Simon 2007 formal proof) |
| 後続著者による formal proof | 後続 information theory 全体 | 後続 algorithmic information theory | Kurtz-Simon 2007 (Σ_2^0-complete) |
= Conway FRACTRAN は Shannon-Kolmogorov 型 の 3 番目 direct analog (藤本さん 2026-08-11 turn 明示指摘)。 「本人が 枠を 引き、 外側を 自分で 指した」 の 3 要件 全 一致。 STEP 1318 backlog #11 Büchi 95% 境界 で 「Collatz 1937 は 問題文のみ で Shannon-Kolmogorov 型 と 同型でない」 と Rei-side 「独立到達」 narrative を 撤回した が、 Conway FRACTRAN は 「Collatz を 含む 問題族 の self-limitation」 という 意味で 「Shannon-Kolmogorov 型」 の 直接 analog 成立。
6.2 実質的な問い: 3n+1 の 位置
open question (藤本さん 2026-08-11 turn 引用): 「3n+1 単体が その 決定不能な 領域の 内側にあるのか 外側にあるのか、 それが 実質的な問いになる」
- 可能性 1: 3n+1 は 決定可能な 部分族 の 内側 (Collatz 予想 が 解ける) = Rei stack の STEP 622-624 THE_THEOREM chain + STEP 1274 ThreeAdicIsolation 系の 積み上げ が 「決定可能側」 の evidence layer に 位置
- 可能性 2: 3n+1 は 決定不能族 の 特殊 case (Kurtz-Simon 2007 の undecidability が 3n+1 に も 適用) = Rei-side Findings 3-7 の 「Lyapunov 系列全体 突破不能」 (STEP 1310-1319 arc) が 「決定不能側」 の 傍証 (訂正 framing per: 「写像の 定義から Lyapunov 組めない = 局所-大域 gap」)
= 可能性 1 vs 可能性 2 は 現状 open、 Rei-side は どちら 立場も 取らず 「両 direction の operational evidence 提供」 stance 継続 (project_research_only_stance.md + feedback_no_direct_author_contact.md)。
7. Honest scope (6 条)
- novelty ゼロ: Conway 1972 + 1987 + Kurtz-Simon 2007 は 全 外部 prior art。 Rei-side 実装 (Lean 4 formal proof) は 未実施、 novel formalization claim ゼロ。 本 site page は 集約 site 反映のみ。
- direct verify 前 (pending): Conway 1972 「Unpredictable iterations」 + Kurtz-Simon 2007 「The Undecidability of the Generalized Collatz Problem」 の 論文 content 直接 access 未完了。 記述 は 2 次資料 (Wikipedia + Kurtz-Simon 2007 references + Conway 収録論文集) 経由。 直接 verify 完了後 訂正 candidate = Wikipedia Collatz conjecture § Undecidable generalizations + SpringerLink LNCS 4484 pp. 542-553 direct fetch は 別 turn candidate。
- 3n+1 specific は open: Kurtz-Simon 2007 は 「任意 (q, d)」 の 決定不能性、 3n+1 (T_{3,1}) の specific decidability/undecidability は 明示的 に 触れていない (memory 内 verify 前)。 「決定不能族 の 内側 or 外側」 は open question。 Rei-side は どちら 立場も 取らず、 両 direction の operational evidence 提供 stance 継続。
- 本人保存 洞察 audit 適用:
feedback_collatz_not_shannon_kolmogorov_analog_2026-08-11.mdで 追加した discipline per、 Conway 1972 + 1987 は 「本人が 具体 洞察を 保存した」 論文 (self-authored、 short but 具体 content) = ✅ Shannon-Kolmogorov 型 analog 成立。 Rei-side は 「独立到達」 と framing しない、 「external prior art alignment」 のみ。 - Rei-side is site 反映のみ: Conway FRACTRAN + Kurtz-Simon 2007 formal proof を Rei-side で Lean 4 formal proof に 実装するのは 数ヶ月 work + novelty ゼロ +
feedback_external_community_outreach_premature.mdtension = defer 継続。 本 STEP 1320 は site 反映 primary + Rei stack との relationship 明示のみ。 - 「t1」 label は Rei-side 未使用: 藤本さん 2026-08-11 turn で 使用の 「t1」 label は Rei-side 「trailing ones」 で 表記、 FRACTRAN encoding では 「v_2(3n+1)」 (2-adic valuation) 表記 使用。 semantic mapping は 一致、 label naming の 差 明示 (STEP 1318 と 同 pattern)。
8. 関連 memory + 関連 site page + Rei stack accumulation impact
8.1 関連 memory
feedback_collatz_not_shannon_kolmogorov_analog_2026-08-11.md(STEP 1318 で 追加、 本 STEP で 「本人保存 洞察 audit」 discipline 適用 実例)project_2026-08-10_multi_project_pause_state.md(Tier 3 candidate list origin)project_defer_records_2026-08-10.md(9 defer records の 拡張 pattern per、 本 STEP は Tier 3 site 反映 が defer から 起動 pattern)feedback_chat_claude_hallucination_warning.mdPattern 2 self-detection (Kurtz-Simon 2007 論文 content 直接 verify 前 = Pattern 2 accepted)feedback_evaluation_symmetry_principle.md(Conway + Kurtz-Simon 2007 の inflate せず deflate せず = external prior art fact-based 記述)project_25_load_bearing_inventions.md#5 逆因果 「STEP(t₀) ← EternalRei(t₊∞)」 (「急がず ゆっくりと」 = defer #3 継続 が 「Tier 3 candidate site 反映 が 起動 phase に 移った」 signal)
8.2 関連 site page
- backlog #11 — Büchi 95% 境界 (STEP 1318) (Dhiman-Pandey 2026 automata level 限界、 本 STEP と complementary な Turing-complete level 限界)
- backlog #2 — Chang v6 29 paradigm exhaustion (「decidability / computability」 paradigm cell mapping)
- backlog #1 — Paper 145 v0.9-c 4-substrate methodology (Rei-side operational evidence layer 前例)
- Rei blueprint pilot (STEP 1310) (STEP 622-624 THE_THEOREM chain、 3n+1 specific decidability 側の Rei-side 積み上げ)
- t1 Lyapunov Verifier (STEP 1311) (Findings 3-7、 3n+1 specific の 「Lyapunov 突破不能」 傍証 = 決定不能側 の 傍証)
- backlog #5 — 25 load-bearing inventions (#5 逆因果 「急がず ゆっくりと」 継承)
8.3 Rei stack accumulation impact
| 項目 | 本 STEP 1320 の impact |
|---|---|
| Papers | 176 (変更なし、 novelty ゼロ) |
| SEED_KERNEL | 1,675 (変更なし) |
| Lean 4 axiom-free | 3,471 (変更なし、 Conway FRACTRAN Lean 4 実装は defer 継続) |
| Chang paradigm coverage | 20/29 = 69.0% (変更なし、 「decidability / computability」 cell は 未 retrofit のまま、 本 STEP で mapping 明示のみ) |
| Backlog | Tier 1+2 完 10/10 + Tier 3 #1 (backlog #11 Büchi 95% 境界) + 本 #12 = Tier 3 「本当に情報量が高い場所」 の 2 番目 追加 |
| Shannon-Kolmogorov 型 direct analog map | Rei stack 内 で Conway FRACTRAN = 3 番目 analog (Shannon 1951 + Kolmogorov 1974 + Conway 1972/1987) 明示化。 Collatz 1937 は analog 不成立 confirm (STEP 1318 継承)。 |
| 2 axis 限界 明示化 | automata level (Dhiman-Pandey 2026、 STEP 1318) + Turing-complete level (Conway-Kurtz-Simon、 本 STEP 1320) の 2 axis complementary が Rei stack 内 で 完成 |
8.4 Tier 3 残 candidate #3 継続
Tier 3 「本当に情報量が高い場所」 candidate:
- #1 Büchi 95% 境界 = STEP 1318 で 反映済
- #2 Conway FRACTRAN 決定不能性 = 本 STEP 1320 で 反映済
- #3 Terras 1976 stopping time density + Everett 1977 log-density = 継続 defer (density 結果 = orbit の 統計的性質 (almost all n の 挙動)、 Terence Tao 2019 「almost all n」 の 先駆、 Rei-side は Rozier-Terracol log ratio が 別 direction で 実装済、 Terras/Everett direct 実装 は 未実施)
#3 の 起動判断は 藤本さん judgment 継続待ち。 direction (α) 完全 Lean 4 formal proof 実装 は 数ヶ月 work + novelty ゼロ、 direction (γ) site 反映のみ は 1-2 turn work で execution cost 低。