/* lawspace.c — edge-of-chaos search over a space of lawful computations.
*
* Rung 0 of the ladder: which LAWS (rule-sets) support complex/life-like
* computation? Langton's lambda (1990) parameterizes a space of lawful rules —
* cellular automata (local + composable + a quiescent "vacuum" state) — by ONE
* number: lambda = fraction of the rule table that maps to a NON-quiescent state
* (how much the law "lets happen"). Sweep lambda 0->1 and measure complexity.
*
* Complexity metric = spatial MUTUAL INFORMATION between adjacent cells:
* lambda low (ordered) : everything dies to the vacuum -> cells identical -> MI 0
* lambda high (chaotic) : cells independent noise -> MI ~ 0
* lambda EDGE (complex) : correlated propagating structure -> MI PEAKS
* The peak is the narrow critical band of lawful rules that support the bootstrap
* (Langton's "edge of chaos"; Wolfram Class IV). Same criticality thread as the
* laser / Mess3 symmetry-breaking: lawful AND poised at the edge.
*
* build: cc -O2 -Wall -std=c11 -o lawspace lawspace.c -lm
*/
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define K 4 /* states per cell (state 0 = quiescent "vacuum") */
#define NB 3 /* neighborhood size (radius 1) */
#define NC (K*K*K) /* rule-table entries = K^NB = 64 */
#define L 600 /* lattice size (periodic) */
#define T 600 /* time steps */
#define W 250 /* measure over the last W steps */
#define RULES 64 /* random rules averaged per lambda */
static unsigned long long RNG;
static unsigned long long xs(void){ RNG^=RNG<<13; RNG^=RNG>>7; RNG^=RNG<<17; return RNG; }
static double urand(void){ return (double)(xs()>>11)*(1.0/9007199254740992.0); }
/* a lawful rule-set of "activity" lambda: table[nbhd]->state; vacuum is a fixed point */
static void build_rule(int *tab,double lambda){
tab[0]=0; /* all-quiescent -> quiescent (a vacuum) */
for(int c=1;c<NC;c++) tab[c]=(urand()<lambda)? 1+(int)(xs()%(K-1)) : 0;
}
/* run one CA, return spatial MI (bits) between adjacent cells + single-cell entropy */
static void run_ca(const int *tab,double *mi_out,double *h_out){
static int s[L],n[L];
for(int i=0;i<L;i++) s[i]=(int)(xs()%K);
long joint[K][K],marg[K]; long tot=0;
for(int a=0;a<K;a++){ marg[a]=0; for(int b=0;b<K;b++) joint[a][b]=0; }
for(int t=0;t<T;t++){
for(int i=0;i<L;i++){
int l=s[(i-1+L)%L],c=s[i],r=s[(i+1)%L];
n[i]=tab[l*K*K + c*K + r];
}
for(int i=0;i<L;i++) s[i]=n[i];
if(t>=T-W){
for(int i=0;i<L;i++){ int a=s[i],b=s[(i+1)%L]; joint[a][b]++; marg[a]++; tot++; }
}
}
double mi=0,h=0;
for(int a=0;a<K;a++){
double pa=(double)marg[a]/tot; if(pa>0) h+=-pa*log2(pa);
for(int b=0;b<K;b++){
double pab=(double)joint[a][b]/tot; if(pab<=0) continue;
double pb=(double)marg[b]/tot; /* marg is symmetric in the stationary lattice */
mi+=pab*log2(pab/(pa*pb));
}
}
*mi_out=mi; *h_out=h;
}
int main(void){
printf("=== EDGE-OF-CHAOS LAW-SPACE SEARCH (Langton lambda, K=%d) ===\n",K);
printf(" complexity = spatial mutual information between adjacent cells (bits)\n");
printf(" %-8s %10s %10s\n","lambda","MI(bits)","H(bits)");
double best_mi=-1,best_lam=0;
for(int li=1;li<=19;li++){
double lam=li*0.05;
double mi_sum=0,h_sum=0;
for(int r=0;r<RULES;r++){
RNG=0x9e3779b97f4a7c15ULL + (unsigned long long)(li*1000+r)*0x2545F4914F6CDD1DULL;
static int tab[NC]; build_rule(tab,lam);
double mi,h; run_ca(tab,&mi,&h); mi_sum+=mi; h_sum+=h;
}
double mi=mi_sum/RULES, h=h_sum/RULES;
if(mi>best_mi){ best_mi=mi; best_lam=lam; }
/* little bar for the MI */
int bar=(int)(mi*40+0.5); char b[64]; for(int k=0;k<bar&&k<60;k++)b[k]='#'; b[bar<60?bar:60]=0;
printf(" %-8.2f %10.4f %10.4f %s\n",lam,mi,h,b);
}
printf("\n PEAK complexity at lambda = %.2f (MI=%.4f bits) — the edge of chaos.\n",best_lam,best_mi);
printf(" Ordered (low lambda) and chaotic (high lambda) both -> low MI; only the\n");
printf(" critical band supports complex computation. THAT is the lawful sliver.\n");
return 0;
}