[Pli 7 Origami Wolfram] Kolmogorov structure function Rule 30 / Rule 110

Suite Origami Wolfram — pli 7.

Perimetre

Pli 4 (PR #19815 c.109, PR #19819 c.110) a montre que la compression LZ fenetree (K_trajectory) ne discrimine pas Rule 30 (classe III chaotique) de Rule 110 (classe IV Turing-complet) — les deux collapsent a ratio 0.510, indistinguables.

Pli 7 implemente un discriminant different : la Kolmogorov structure function (Vereshchagin & Vitanyi 2004, Li & Vitanyi 2019 ch. 6) — K(W|W') mesure la complexite conditionnelle d'une trajectoire W sachant une sous-sequence W'. Theoreme central : pour une trajectoire aleatoire (entropie maximale), K(W|W') tend vers K(W) + 0 (W' n'aide pas) ; pour une trajectoire structuree, K(W|W') << K(W) (W' est un raccourci vers la description). Discrimination fine Rule 30 vs Rule 110 par K(W|W') est falsifiable.

Strategie

1. Implementer measure_wolfram_ksf(n_cells, n_steps, seed) dans scripts/hashlife/k_trajectory.py : pour chaque regle (R0, R4, R30, R110), mesure K(W_t | W_t-W') pour W' dans [1, 2, 4, 8, 16, 32] cellules de contexte. LZ compresse la concatenation [W_t-W' ; W_t], K(W_t | W_t-W') := len(LZ([W_t-W' ; W_t])) - len(LZ(W_t-W')).
2. Verdict par classe : KSF pour R30 doit tendre vers une asymptote non-nulle (chaos 1-D a entropie lineaire en temps, contexte ne reduit pas significativement), KSF pour R110 doit tendre vers 0 ou croitre lentement (Turing-complet : la sous-sequence W_t-W' capture une partie du programme, contexte aide). Discrimination = difference d'asymptote entre R30 et R110.
3. Verdict falsifiable : si KSF asymptotique R30 == KSF asymptotique R110 (meme bruit) -> REFUTE la discrimination par KSF (comme pli 4 par LZ). Si KSF asymptotique R30 != KSF asymptotique R110 -> CONFIRME la discrimination par KSF, et le discriminant est adequate pour Turing vs chaos 1-D.

Livrables

• scripts/hashlife/k_trajectory.py : mode --wolfram-ksf (+/-200 lignes) avec WOLFRAM_KSF_LANDMARKS (asymptotes), measure_wolfram_ksf, wolfram_ksf_verdict, wolfram_ksf_discrimination_verdict
• scripts/hashlife/wolfram_ksf_results.json : verbatim mesure 4 classes × 6 contextes = 24 mesures
• scripts/hashlife/WOLFRAM-VERDICT-KSF.md (NEW) : falsifiable verdict documentant la discrimination (ou son absence)
• scripts/hashlife/tests/test_wolfram_ksf.py : 6-8 tests pytest (KSF constantes, mesure 24 entrees, verdict par classe, discrimination R30 vs R110, JSON round-trip)
• scripts/hashlife/README.md (MAJ) : table des 6 modes CLI + ligne pli 7 dans resultats

Reproduction

export PYTHONPATH=MyIA.AI.Notebooks/IIT/ICT-Series
python scripts/hashlife/k_trajectory.py --mode wolfram-ksf --n-cells 64 --n-steps 64
python scripts/hashlife/k_trajectory.py --mode wolfram-ksf --n-cells 64 --n-steps 64 \
    --json-out scripts/hashlife/wolfram_ksf_results.json
PYTHONPATH=MyIA.AI.Notebooks/IIT/ICT-Series \
  python -m pytest scripts/hashlife/tests/test_wolfram_ksf.py -v

Hypothese de travail (a valider ou infirmer)

• R0 (I) : KSF tres bas des le depart (constance -> 0 entropie).
• R4 (II) : KSF bas, periodicite -> contexte capture tout.
• R30 (III) : KSF eleve, contexte n'aide pas ou pas beaucoup.
• R110 (IV) : KSF intermediaire, contexte aide partiellement (Turing-complet a de la redondance locale grace aux gliders).

Si KSF discrimine R30 de R110, c'est un resultat positif (vs pli 4 LZ qui REFUTAIT). Si KSF ne discrimine pas non plus, ca renforce la these que les complexites de trajectoire 1-D ne distinguent pas Turing-complet du chaos — il faut un instrument plus structurel (block decomposition, SAT-based minimal program).

Sources

• Vereshchagin, N. & Vitanyi, P. (2004). Kolmogorov structure functions and model selection. IEEE Trans. Info. Theory 50(12): 3265-3290.
• Li, M. & Vitanyi, P. (2019). An Introduction to Kolmogorov Complexity and Its Applications. Springer. 4th ed. Ch. 6-7.
• Wolfram, S. (2002). A New Kind of Science. Ch. 7 (Rule 110 Turing-completude).

Suite Origami

Pli 5 (regles reecriture hypergraphes Lean) et pli 6 (graphe multiway lake Lean) bloques par env Lean/JVM absent (voir dashboard workspace-CoursIA-2). Pli 7 est executable sur po-2024 (Python local).

Co-Authored-By: Claude Haiku 4.5 (1M context) noreply@anthropic.com

🤖 Generated with Claude Code

Part of #19742 (EPIC Origami)