Paper 96: The Semi-Infinite Circuit Hypothesis — How Large Must a Circuit Be to Decide the Collatz Conjecture?
Author: Fujimoto Nobuki (藤本伸樹) / fc0web
Date: 2026-04-16 | License: CC-BY-4.0
Keywords: infinite circuits, hypercomputation, Malament-Hogarth, natural proofs, Razborov-Rudich, Collatz, D-FUMT₈
Abstract
If a finite circuit cannot verify ∀n (Paper 91 §7), what about an infinite one? We survey three distinct notions of infinite circuit — non-uniform families (P/poly), ω-circuits (Turing-equivalent), and hypercomputation (Malament-Hogarth observers) — and give an honest accounting of which unsolved problems each can, in principle, decide. We then propose the central open question: does there exist a finite size N* such that every Collatz-family problem is decidable by an N*-circuit? We connect this to Razborov-Rudich natural proofs (1997) and Aaronson-Wigderson algebrization (2008).
1. Three kinds of "infinite" circuit
| kind | definition | decides |
|---|---|---|
| A. P/poly (non-uniform family) | one finite C_n per input length n | only languages in P/poly (proper subset of all languages) |
| B. ω-circuit (countably many gates, 1 circuit) | Turing-equivalent | computable functions; not halting problem |
| C. hypercomputation (Malament-Hogarth observer) | infinite steps in finite proper time | halting problem, ∀n universal over ℕ |
2. Implications for unsolved problems
| problem | A. non-uniform | B. ω-circuit | C. hypercomputation |
|---|---|---|---|
| Collatz (∀n orbit → 1) | ✗ (Paris-Harrington obstacle) | ✗ | ✓ |
| Goldbach | ✗ | ✗ | ✓ |
| Riemann (on critical line) | ✗ | ✗ | ✓ |
| P vs NP | ✗ (Razborov-Rudich barrier) | ✗ | partial |
| Continuum Hypothesis | ✗ | ✗ | ✗ (ZFC-independent) |
| Whitehead problem | ✗ | ✗ | ✗ (ZFC-independent) |
Key point: hypercomputation resolves computational open problems but not axiomatic ones. The ZFC-independence of the continuum hypothesis (Cohen 1963) is invisible to any circuit size.
3. Physical realizability
| kind | mathematically consistent | physically realizable in our universe |
|---|---|---|
| A | ✓ | depends on the family — often yes for fixed n |
| B | ✓ | approximable up to Bekenstein bound |
| C | ✓ (Etesi-Nemeti 2002, Welch 2008) | ✗ (our universe is FLRW, no Malament-Hogarth worldlines) |
4. The semi-infinite hypothesis
Question: Is there a finite N* such that a circuit of size N* can verify ∀n ∈ ℕ for every Collatz-family instance?
Status: Unknown. Relevant partial obstructions:
- Razborov-Rudich 1997 (natural proofs): any proof-by-circuit satisfying the "largeness" and "constructivity" properties cannot separate strong complexity classes. This suggests N* either does not exist or is astronomically large.
- Aaronson-Wigderson 2008 (algebrization): any arithmetization-relative proof must also fail the Yao-type lower bound.
- However, Collatz might escape both barriers because the underlying statement is Π¹₁, not a complexity-class separation.
5. D-FUMT₈
| circuit kind | D-FUMT₈ |
|---|---|
| finite buildable | TRUE (decidable but bounded) |
| P/poly family | FLOWING (continuous extension) |
| ω-circuit | INFINITY (formal supremum) |
| hypercomputation | BOTH (mathematical yes / physical no) |
| ZFC-independent | NEITHER (no circuit suffices) |
The semi-infinite hypothesis asks whether Collatz sits in TRUE or FLOWING; if a finite N* exists, Collatz is decidable with a buildable device.
6. What Rei can do toward resolution
- Lower-bound experiments: use FPGA + quantum to push empirical verification to 10¹⁵ (the current Collatz record is 10²⁰).
- Upper-bound arguments: attempt an N* construction via D1/D2 + telescoping (Paper 73 + STEP 811).
- Formal investigation: Lean 4 formalization of the reverse-mathematical strength of Collatz (STEP 789 ACA₀ diagnosis).
7. Honest limits
- This paper proposes a hypothesis, not a theorem.
- Malament-Hogarth hypercomputation is a consistency proof inside GR, not a build guide.
- If the hypothesis is false (no finite N* exists), we inherit the full Collatz-is-Π¹₁ open problem.
8. Reproducibility
This is a conceptual / survey paper. No new simulation script. Connects Papers 88 (P vs NP), 91 (electrical circuit), 95 (triple invariant).
CC-BY-4.0