GameTheory-20e – Perplexite structurelle Hashlife : instrument, mesure, et la question Turing-complet
T12 tranche 2 (issue #18446) : ce carnet consomme l’instrument scripts/hashlife/k_trajectory.py (livre par PR #18639 MERGED 2026-10-01 par myia-po-2026:CoursIA-2) et ses resultats scripts/hashlife/k_trajectory_results.json, puis examine la these du pivot probabiliste : la dissolution par fragilite (soupe) versus l’auto-entretien (programme recursif) se distinguent-elles dans la mesure K_trajectory(t, W) = W ?
Le verdict tranche 1, important. L’instrument collapse les programmes Conway simples (glider, blinker, pulsar, OTCA static) au-dela du seuil 0.7 du discriminant, les classant PROGRAM-PERIODIC-COLLAPSED – la periode courte est detectee par LZ, et le quotient K(W=16)/K(W=1) plafonne a 0.15. Les trajectoires de soupe ont un quotient entre 0.76 et 0.78 (classe SOUP-FRAGILE-WEAK), une signature moins compressible que les periodiques mais loin du seuil PROGRAM-AUTO-ENTRETIEN. Aucun temoin du corpus courant ne valide la these d’origine. Tranche 2 discute pourquoi, et propose un test Turing-complet (OTCA replicator, Spartan universal computer) comme banc de confirmation.
1. Chargement des mesures tranche 1
L’instrument est livre par scripts/hashlife/k_trajectory.py (PR #18639, MERGED 2026-10-01 par myia-po-2026:CoursIA-2). Il definit :
K_trajectory(t, W) : longueur compressee LZ (zlib) du flux d’octets de la trajectoire fenetree a W colonnes ; c’est une borne superieure de la complexite de Kolmogorov de la trajectoire.
lz_compressed_length(data) : la primitive de compression utilisee.
Reproducibilite mesuree (po-2024 2026-10-01T10:26Z) : k_trajectory.py --mode measure est rejouable sur ai-01 (Python 3.14.3) a la tete d10d6033. Les resultats chiffres ici proviennent de la sortie JSON livree par la tranche 1 – 7 trajectoires, 5 fenetres W=1,2,4,8,16.
K_trajectory(t, W) pour les 7 trajectoires du corpus, fenetre W = 2^n, n = 0..4 (donc W = 1, 2, 4, 8, 16). La trajectoire est codee en flux d’octets (1 bit par cellule, MSB first dans chaque octet, ligne par ligne). Les lignes du tableau sont les programmes periodiques simples (haut) et les soupes (bas).
import pandas as pdrows = []for r in data['results']: rows.append({'trajectoire': r['trajectory'],'W': r['W'],'K_trajectory': r['k_trajectory'], })df = pd.DataFrame(rows)pivot_k = df.pivot(index='trajectoire', columns='W', values='K_trajectory')pivot_k.columns = [f'W={c}'for c in pivot_k.columns]pivot_k
W=1
W=2
W=4
W=8
W=16
trajectoire
blinker_T2
240
160
92
46
25
glider_T4
280
200
152
82
43
otca_static
352
200
100
50
27
pulsar_T3
437
319
196
101
54
soup_d03_seed42
625
558
519
500
476
soup_d05_seed123
640
568
534
518
486
soup_d05_seed777
643
583
546
524
504
3. Le discriminant en echelle log-log
L’idee d’origine (these user 10:46Z sur #18379) : pour une trajectoire recursive, le quotient K_trajectory(t, W) / W reste borne inferieureurement par une constante > 0 quand W croit ; pour une trajectoire de soupe, il tend vers 0. Cela se traduit graphiquement par :
Programme recursif : sur un graphe log(K) vs log(W), la courbe reste au-dessus d’une asymptote de pente 1 (K proportionnel a W).
Soupe : la courbe tend vers une pente < 1 (K sous-lineaire en W).
import mathprint('--- pentes log-log (delta log K / delta log W) ---')ws =sorted(pivot_k.columns, key=lambda c: int(c.replace('W=', ''))) # tri numerique : W=1,2,4,8,16ws_num = [int(c.replace('W=', '')) for c in ws]for traj in pivot_k.index: ks = pivot_k.loc[traj, ws].values slopes = []for i inrange(1, len(ws)): slope = (math.log10(ks[i]) - math.log10(ks[i-1])) / (math.log10(ws_num[i]) - math.log10(ws_num[i-1])) slopes.append(slope)print(f'{traj:30s}: pentes = {[round(s, 2) for s in slopes]}')
Lecture du resultat – ce que les pentes mesurees disent
Sur le corpus courant, toutes les pentes mesurees sont negatives ou quasi nulles : aucune trajectoire ne suit l’asymptote de pente 1 annoncee par la these. Ce qui discrimine est l’amplitude de la decroissance, pas le signe : les periodiques courtes (glider T=4, blinker T=2, pulsar T=3, OTCA static) chutent de -0.4 a -1.0 par doublement de W – otca_static atteint exactement -1.0 sur W=2 -> W=4, soit log2(100/200) = -1, sa complexite mesuree est inversement proportionnelle a W – tandis que les soupes restent quasi plates, de -0.04 a -0.17 (soup_d05_seed777 W=2 -> W=4 : log2(546/583) = -0.09). La periode courte est compressible des la fenetre W=2 ; les soupes ne se compressent que marginalement quand W croit.
4. Pourquoi les periodiques courts sont classes PROGRAM-PERIODIC-COLLAPSED
Le discriminant officiel tranche 1 (K(W=16) / K(W=1) < 0.7) marque PROGRAM-PERIODIC-COLLAPSED les motifs dont la trajectoire devient tres compressible a grande fenetre. Cela reflete la periode courte (P2 / P3 / P4), pas une absence d’auto-entretien.
L’instrument mesure l’entropie LZ, pas l’auto-entretien.
Un motif periodique de periode p produit un flux d’octets ou le bloc de p colonnes se repete indefiniment : K_trajectory(t, W) plafonne tres vite au-dela de W=p (la repetition capture toute l’information dans une copie). A l’inverse, un programme non periodique (mais Turing-complet : OTCA replicator a la periode 3530M, Spartan universal computer) maintiendrait sa complexite a toutes les echelles de W.
Les seuils tranches 1 sont donc :
< 0.7 : PROGRAM-PERIODIC-COLLAPSED – motif periodique a periode tres inferieure a W=16 ; l’instrument collapse.
[0.7, 0.95) : SOUP-FRAGILE-WEAK – entropie non negligeable qui ne se reduit que partiellement quand W croit.
>= 0.95 : PROGRAM-AUTO-ENTRETIEN – aucune mesure sur le corpus courant.
Le discriminant ne discrimine pas soupe vs programme. Il discrimine periodique-court vs non-periodique. Les periodiques courts du corpus sont des cas triviaux qui ne mettent pas en valeur la capacite distinctive d’un programme Turing-complet.
# Visualisation du discriminant pour les 7 trajectoiresdiscriminants = []for traj in pivot_k.index: k1 = pivot_k.loc[traj, 'W=1'] k16 = pivot_k.loc[traj, 'W=16'] ratio = k16 / k1 verdict = data['verdicts'].get(traj, '') discriminants.append({'trajectoire': traj,'K(W=1)': k1,'K(W=16)': k16,'ratio K(W=16)/K(W=1)': round(ratio, 4),'verdict tranche 1': verdict.split('(')[0].strip(), })disc_df = pd.DataFrame(discriminants)disc_df
trajectoire
K(W=1)
K(W=16)
ratio K(W=16)/K(W=1)
verdict tranche 1
0
blinker_T2
240
25
0.1042
PROGRAM-PERIODIC-COLLAPSED
1
glider_T4
280
43
0.1536
PROGRAM-PERIODIC-COLLAPSED
2
otca_static
352
27
0.0767
PROGRAM-PERIODIC-COLLAPSED
3
pulsar_T3
437
54
0.1236
PROGRAM-PERIODIC-COLLAPSED
4
soup_d03_seed42
625
476
0.7616
SOUP-FRAGILE-WEAK
5
soup_d05_seed123
640
486
0.7594
SOUP-FRAGILE-WEAK
6
soup_d05_seed777
643
504
0.7838
SOUP-FRAGILE-WEAK
5. Le test Turing-complet qui manque : OTCA replicator et Spartan
L’echec de l’instrument tranche 1 est diagnostique : il n’a pas ete applique a un temoin Turing-complet. Les periodiques courtes sont triviales ; les periodiques longues (milliards de generations) ou non-periodiques (universal computers) sont la cible.
Trois candidats documentes dans la litterature :
OTCA metapixel (Hein, 2009) : un meta-automate 7578 x 7578 qui simule n’importe quel automate cellulaire par inclusion. Sa periode, dans la metapixel, equivaut a celle de l’automate simule. Pour simuler Conway sur 100 generations, la periode OTCA est de l’ordre de 3.5 milliards. Un replicator base sur OTCA produit une periode du meme ordre de grandeur.
Spartan universal constructor (Boyle, 2008) : un macrostructure qui peut etre programmee pour executer n’importe quel algorithme, sans periodicite ferme (la periode depend du programme). Sa trajectoire est non-periodique. L’hypothese qu’une telle trajectoire maximise l’entropie LZ reste non mesuree : aucun corpus Spartan n’a ete compresse a ce jour.
Hashlife macrocellulaire (Conway, Goucher, 2014) : une construction hierarchique qui evolue par blocs de 2^(2n) cellules avec memoisation memoise. La trajectoire est une megastructure stable.
Hypothese de travail, non mesuree : ces cibles exigeront des corpus volumineux (possiblement plusieurs megaoctets) dont le cout de generation n’a pas encore ete confronte a l’instrument LZ Python local – la tranche 3 tranchera par la mesure. La tranche 3 (futur) pourrait les servir : OTCA etant le plus accessible (format RLE largement diffuse).
Justification du verdict CONJECTURE-NON-VERIFIABLE. Les seuils tranches 1 (< 0.7 / 0.7-0.95 / >= 0.95) operent une discrimination periodique vs entropie, pas programme vs soupe. Sans corpus Turing-complet (OTCA ou Spartan), il est impossible de trancher la these d’origine : le discriminant actuel est trop grossier pour separer auto-entretien reel (Turing-complet) de bruit entropique (soupe stationnaire).
6. Verdict falsifiable
Le pivot probabiliste du user (these 10:46Z, #18379) postule que K_trajectory(t, W) / W tend vers 0 pour la soupe et reste borne inferieureurement pour les programmes recursifs. Cette these n’est pas verifiee par le corpus tranche 1. Les periodiques courts (glider, blinker, pulsar, OTCA static) sont classes PROGRAM-PERIODIC-COLLAPSED, et les soupes sont SOUP-FRAGILE-WEAK. Aucun temoin du corpus courant n’atteint le seuil PROGRAM-AUTO-ENTRETIEN.
L’instrument K_trajectory(t, W) mesure la compressibilite LZ, qui discrimine periodique-court vs entropie-stationnaire, mais pas auto-entretien vs dissolution-par-fragilite (le discriminant annonce). Pour discriminer ces deux regimes il faudrait :
Un corpus Turing-complet (OTCA replicator, Spartan universal computer) pour mesurer le quotient sur une trajectoire non-periodique massivement complexe. Le banc n’est pas accessible dans l’instrument tranche 1 (limite memoire).
Un invariant different – a condition de distinguer trois notions de complexite. (a) La longueur zlib que mesure l’instrument : bornee par le format de description LZ et les ressources du compresseur. (b) La complexite de Kolmogorov ideale : pour TOUT programme deterministe fixe P (regle de Life et graines comprises), le prefixe de T generations se decrit par P et T, donc sa complexite est au plus K(P) + O(log T) – la completude de Turing n’etablit PAS une croissance lineaire incompressible au sens ideal, et K(t)/T -> 0 pour toute trajectoire deterministe. (c) Une complexite bornee en ressources (temps ou memoire de description limites) : seul regime ou la distinction programme vs soupe peut survivre, car decrire la soupe exige de rejouer le calcul integralement tandis qu’un replicateur porte sa propre description courte. La these d’origine n’a de contenu operationnel que dans les regimes (a) et (c), pas au sens ideal (b).
Un test dual reformule en complexite bornee en ressources : au sens ideal, K(t) / T -> 0 pour toute trajectoire deterministe (borne K(P) + O(log T) ci-dessus) ; la reformulation operationnelle doit donc mesurer une complexite bornee en ressources – longueur du plus court programme reproduisant t en temps polynomial en T, ou longueur compresse par LZ sur fenetres glissantes. C’est cette version bornee, et elle seule, qui peut separer auto-entretien (taux d’information maintenu sous contrainte de ressources) de dissolution par fragilite.
7. Conclusion
L’instrument scripts/hashlife/k_trajectory.py est correct : il calcule K_trajectory(t, W) et distingue les periodiques courts des entropies moyennes. Mais le pivot annonce – K_trajectory(t, W) / W -> 0 (soupe) vs constante (programme) – n’est pas verifie par le corpus tranche 1. L’instrument n’a pas ete confronte a un temoin Turing-complet.
Cette tranche 2 documente cet ecart et propose trois pistes pour tranche 3 (corpus OTCA, invariant conditionnel, moyenne glissante). Elle ne livre pas de tranche 3 : le travail a faire est substantiel (corpus megaoctets) et dependra d’un arbitrage user sur la these reformulee.
Statut : tranche 2 livree, instrument tranche 1 valide, these pivot NON VERIFIEE par les mesures disponibles.
Predecesseur : GameTheory-20d (Loi II, seconde jambe : synthetiser un translateur Life). Le present carnet prend la releve sur le meme substrat Conway mais transpose le probleme verify-once (verificateur de validite d’un translateur) vers le probleme measure-once (instrument K_trajectory qui mesure l’entropie LZ d’une trajectoire fenetree).
Le discriminant tranche 1 utilise le seuil 0.7 pour separer PROGRAM-PERIODIC-COLLAPSED de SOUP-FRAGILE-WEAK. Reproduisez le calcul pour le seuil 0.5 et 0.9. Combien de trajectoires changent de classe ? Le seuil 0.7 est-il robuste ?
Exercice 2 – Normalisation par la dimension.
Chaque trajectoire est codee en flux d’octets de dimensions differentes (glider 16x16, OTCA 7578x7578). K_trajectory depend-il de la dimension ? Proposez une normalisation (par exemple K_trajectory(t, W) / (rows * W)) et observez comment le discriminant evolue.
Exercice 3 – Compresseur alternatif.
L’instrument utilise zlib (LZ77). Si on dispose d’un compresseur PPM (par exemple ppmd-py ou zppy), la borne superieure de Kolmogorov est-elle plus serree ? Tracez le quotient K_PPM(t, W) / K_LZ(t, W) sur les 7 trajectoires. La discrimination periodique-court vs entropie tient-elle ?