Paper 72 — Semantic Complexity vs Kolmogorov Complexity

Companion code for:

• Paper 72 — Semantic Complexity as Conditional Kolmogorov Complexity: K_sem(x) ≤ K(x|C) ≤ K(x) — A Formal Bridge from Beyond-Shannon to AIT (forthcoming Zenodo DOI)
• Paper 25 — Beyond Shannon: Generative Compression via Śūnyatā Recreator DOI: 10.5281/zenodo.19392210
• Paper 71 — Reproducibility Package for Beyond-Shannon Compression Repo: https://github.com/fc0web/rei-shannon-demo

Author: Nobuki Fujimoto (藤本 伸樹), Rei-AIOS Project · License: CC-BY-4.0

---

What this demo proves

The chain of inequalities

K_sem(x)  ≤  K(x | C)  ≤  K(x)

is the standard conditional-Kolmogorov result (Li & Vitányi 1997, Theorem 2.2.1) applied to a context dictionary C derived from Rei-AIOS theorem prose.

This empirically grounds Paper 25's "beyond-Shannon" claim inside the established conditional-K framework: Paper 25 is not a violation of Shannon's theorem; it is a special case of the conditional-K reduction where C is the SEED_KERNEL of pre-shared theorems.

Empirical results (5 samples, reproducible)

Context dictionary C: 2 352 bytes (2.30 KB)

sample1-mathematics  orig=659B  K=394B  K(x|C)=353B  K_sem=185B  K_sem/K=47.0%
sample2-physics      orig=753B  K=441B  K(x|C)=384B  K_sem=197B  K_sem/K=44.7%
sample3-philosophy   orig=861B  K=476B  K(x|C)=402B  K_sem=201B  K_sem/K=42.2%
sample4-computing    orig=942B  K=521B  K(x|C)=461B  K_sem=193B  K_sem/K=37.0%
sample5-biology      orig=917B  K=512B  K(x|C)=442B  K_sem=215B  K_sem/K=42.0%

TOTAL                orig=4132B  K=2344B  K(x|C)=2042B  K_sem=991B
AVERAGE              K_sem/K=42.6%   K_sem/K(x|C)=48.8%
Chain holds for ALL 5 samples? YES

• K(x) ≈ |deflateRaw(x)| (Kolmogorov upper bound via Shannon-compliant compression)
• K(x | C) ≈ |deflateRaw(x, dict=C)| (RFC 1951 preset dictionary)
• K_sem(x, C) = |JSON.stringify(seed)| where seed = {category, ctxRefs, delta, structure}

Quick start

git clone https://github.com/fc0web/rei-semantic-complexity
cd rei-semantic-complexity
npm install
npx tsx demo.ts          # runs all 5 samples
npx tsx test.ts          # asserts chain holds (25/25 pass)

Node 18+ only. No Python, no GPU, no learned state.

Method

K(x): unconditional Kolmogorov upper bound

We use zlib.deflateRaw (level 9) as a computable upper bound for K(x). By Shannon's theorem, this is bounded below by the source entropy rate.

K(x|C): conditional Kolmogorov with shared dictionary

We use the same compressor with dictionary: C (RFC 1951 preset dictionary mechanism). This emulates the side-information channel of the conditional Kolmogorov definition.

K_sem(x, C): semantic seed

We extract a four-field seed from x:

interface SemanticSeed {
  category: string;     // mathematics | physics | philosophy | computing | biology
  ctxRefs: number[];    // up to 16 indices into C's token table
  delta:   string[];    // up to 8 tokens NOT in C (the irreducible novelty)
  structure: string;    // DEF/THM markers + sentence count
}

The seed is JSON-serialised and its byte length is reported as K_sem.

Honest scope

This demo is intentionally minimal.

• Context C is a 2.3 KB hand-curated word list — not the full Rei-AIOS SEED_KERNEL of 1,400+ theorems.
• Seed extraction caps ctxRefs at 16 and delta at 8 — Paper 25 production uses unbounded, learned extractors.
• Reconstruction is not part of this demo (Paper 71 covers that).

The point of THIS demo is the inequality chain — that K_sem is provably no larger than K(x|C), which is provably no larger than K(x). The empirical validation across 5 different domains (math/physics/philosophy /computing/biology) is what Paper 72 documents.

Files

demo.ts                   ~270 line self-contained TypeScript demonstration
test.ts                   ~80 line chain-inequality validation
context/
  rei-context-mini.txt    2.3 KB minimal context dictionary
samples/                  5 sample texts (same as Paper 71 for consistency)
package.json              single devDependency: tsx
LICENSE                   CC-BY-4.0
README.md                 this file

Citation

@misc{fujimoto2026paper72,
  author = {Fujimoto, Nobuki},
  title  = {Semantic Complexity as Conditional Kolmogorov Complexity:
            K_sem(x) ≤ K(x|C) ≤ K(x) — A Formal Bridge from Beyond-Shannon to AIT},
  year   = 2026,
  note   = {Paper 72, Rei-AIOS Project. Companion to Paper 25 (DOI 10.5281/zenodo.19392210).}
}

See also

• Paper 25 Beyond Shannon (the original claim): DOI 10.5281/zenodo.19392210
• Paper 69 Schnorr-D-FUMT₈ Correspondence: DOI 10.5281/zenodo.19562346
• Paper 70 Hierarchy of Transcendence: DOI 10.5281/zenodo.19562428
• Paper 71 Reproducibility Package: https://github.com/fc0web/rei-shannon-demo
• Li & Vitányi (1997) An Introduction to Kolmogorov Complexity and Its Applications

Contact

GitHub: fc0web note.com: https://note.com/nifty_godwit2635