/* mess3.c — the REAL fractal falsifier.
*
* Mess3: a 3-state, 3-symbol edge-emitting HMM whose belief (mixed-state) set is
* a genuine FRACTAL on the 2-simplex (Sierpinski-like) — the canonical process
* used to show fractal belief geometry (Shai et al., "Transformers represent
* belief state geometry", NeurIPS 2024). Exact tensor from that paper:
* parameters a=0.9, x=0.075, b=(1-a)/2=0.05, y=1-2x=0.85, giving
* ay=0.765, ax=0.0675, by=0.0425, bx=0.00375. T[s][i][j]=P(emit s, next j | i).
*
* Unlike the SNS (countably-infinite causal states that CONVERGE geometrically,
* so a finite tree matches optimal), Mess3's mixed states DO NOT converge — they
* spread fractally over the simplex. Falsification target:
* 1. the finite ternary PST leaves a MEASURABLE gap below the optimal filter;
* 2. the count of distinct belief states GROWS with resolution (fractal
* dimension signature), instead of saturating like the SNS did (~14).
*
* build: cc -O2 -Wall -std=c11 -o mess3 mess3.c -lm
*/
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define K 3 /* alphabet size */
#define DMAX 12
#define MINOBS 50
#define CHI2_CRIT 13.816 /* chi-squared df=2, p<0.001 */
#define ALPHA 1.0
/* Mess3 transition-emission tensor T[s][i][j] = P(emit s, next state j | i). */
static const double T[K][K][K] = {
/* symbol 0 */ {{0.765,0.00375,0.00375},{0.0425,0.0675,0.00375},{0.0425,0.00375,0.0675}},
/* symbol 1 */ {{0.0675,0.0425,0.00375},{0.00375,0.765,0.00375},{0.00375,0.0425,0.0675}},
/* symbol 2 */ {{0.0675,0.00375,0.0425},{0.00375,0.0675,0.0425},{0.00375,0.00375,0.765}},
};
/* ---- deterministic PRNG ---- */
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); }
/* ---- Mess3 generator ---- */
static void gen_mess3(unsigned char *out, int n){
int s = 0;
for (int i = 0; i < n; i++){
double u = urand(), acc = 0.0;
int es = 0, nj = 0, done = 0;
for (int sym = 0; sym < K && !done; sym++)
for (int j = 0; j < K && !done; j++){
acc += T[sym][s][j];
if (u < acc){ es = sym; nj = j; done = 1; }
}
out[i] = (unsigned char)es;
s = nj;
}
}
/* ============ finite ternary PST ============ */
typedef struct Node { long c[K]; struct Node *ch[K]; int minted; } Node;
static Node *newnode(void){ return calloc(1, sizeof(Node)); }
static long total(const Node *n){ long t=0; for(int s=0;s<K;s++) t+=n->c[s]; return t; }
static double psym(const Node *n, int s){ return (n->c[s]+ALPHA)/(total(n)+K*ALPHA); }
static void build(Node *root, const unsigned char *s, int n){
for (int t = 1; t < n; t++){
Node *node = root; node->c[s[t]]++;
for (int L = 1; L <= DMAX && t - L >= 0; L++){
int a = s[t-L];
if (!node->ch[a]) node->ch[a] = newnode();
node = node->ch[a];
node->c[s[t]]++;
}
}
}
static double gtest(const Node *child, const Node *parent){
long N = total(child); if (!N) return 0.0;
double G = 0.0;
for (int s = 0; s < K; s++)
if (child->c[s] > 0) G += (double)child->c[s] * log((double)child->c[s] / ((double)N * psym(parent, s)));
return 2.0 * G;
}
static int grow(Node *root){
root->minted = 1;
Node **queue = malloc(sizeof(Node*) * (1<<20)); int head=0, tail=0; queue[tail++]=root;
int created = 0;
while (head < tail){
Node *node = queue[head++];
for (int a = 0; a < K; a++){
Node *ch = node->ch[a];
if (ch && total(ch) >= MINOBS && gtest(ch, node) >= CHI2_CRIT){
ch->minted = 1; created++;
if (tail < (1<<20)) queue[tail++] = ch;
}
}
}
free(queue);
return created;
}
static const Node *ctx(const Node *root, const unsigned char *s, int t){
const Node *node = root;
for (int L = 1; L <= DMAX && t - L >= 0; L++){
int a = s[t-L];
if (node->ch[a] && node->ch[a]->minted) node = node->ch[a];
else break;
}
return node;
}
static double logloss_pst(const Node *root, const unsigned char *s, int n){
double ll = 0; long k = 0;
for (int t = DMAX; t < n; t++){ ll += -log(psym(ctx(root, s, t), s[t])); k++; }
return ll / (double)k;
}
/* count minted leaves = PST's causal-state estimate */
static int NLEAF;
static void countleaf(Node *n){
if(!n) return;
if(n->minted){
int deeper=0; for(int a=0;a<K;a++) if(n->ch[a]&&n->ch[a]->minted) deeper=1;
if(!deeper) NLEAF++;
}
for(int a=0;a<K;a++) countleaf(n->ch[a]);
}
/* ============ exact 3-state belief filter (the MSP / optimal predictor) ============ */
static double filter_logloss(const unsigned char *s, int n){
double b[K] = {1.0/3,1.0/3,1.0/3};
double ll = 0; long k = 0;
for (int t = 0; t < n; t++){
int x = s[t];
double px = 0.0, nb[K] = {0,0,0};
for (int i = 0; i < K; i++) for (int j = 0; j < K; j++){
double m = b[i]*T[x][i][j]; nb[j] += m; px += m;
}
if (px < 1e-300) px = 1e-300;
ll += -log(px); k++;
for (int j = 0; j < K; j++) b[j] = nb[j]/px;
}
return ll / (double)k;
}
/* distinct belief states visited, quantized on a G x G grid over the 2-simplex. */
static long filter_distinct(const unsigned char *s, int n, int G){
double b[K] = {1.0/3,1.0/3,1.0/3};
char *seen = calloc((size_t)(G+1)*(G+1), 1);
long distinct = 0;
for (int t = 0; t < n; t++){
int q0 = (int)(b[0]*G + 0.5), q1 = (int)(b[1]*G + 0.5);
if(q0<0){q0=0;} if(q0>G){q0=G;} if(q1<0){q1=0;} if(q1>G){q1=G;}
size_t key = (size_t)q0*(G+1)+q1;
if(!seen[key]){ seen[key]=1; distinct++; }
int x = s[t];
double px = 0.0, nb[K] = {0,0,0};
for (int i = 0; i < K; i++) for (int j = 0; j < K; j++){ double m=b[i]*T[x][i][j]; nb[j]+=m; px+=m; }
if (px < 1e-300) px = 1e-300;
for (int j = 0; j < K; j++) b[j] = nb[j]/px;
}
free(seen);
return distinct;
}
int main(void){
const int NTR = 2000000, NTE = 4000000;
unsigned char *tr = malloc(NTR), *te = malloc(NTE);
RNG = 0x9e3779b97f4a7c15ULL; gen_mess3(tr, NTR);
RNG = 0xd1b54a32d192ed03ULL; gen_mess3(te, NTE);
Node *root = newnode();
build(root, tr, NTR);
int created = grow(root);
NLEAF = 0; countleaf(root);
double ll0 = 0; long k=0;
for (int t=0;t<NTE;t++){ ll0 += -log(psym(root, te[t])); k++; } ll0/=(double)k;
double llp = logloss_pst(root, te, NTE);
double llf = filter_logloss(te, NTE);
printf("=== MESS3 (fractal mixed-state set; a=0.9, x=0.075) ===\n");
printf(" finite ternary PST (our method):\n");
printf(" distinctions created (split) : %d\n", created);
printf(" minted leaf states : %d (DMAX=%d)\n", NLEAF, DMAX);
printf(" log-loss order-0 baseline : %.4f nats\n", ll0);
printf(" log-loss grown world-model : %.4f nats\n", llp);
printf(" exact belief filter (MSP / optimal predictor):\n");
printf(" log-loss (= entropy rate est) : %.4f nats\n", llf);
printf(" gap PST - optimal : %+.4f nats <-- >0 means the finite tool leaves predictability on the table\n", llp - llf);
printf(" FRACTAL PROBE: distinct belief states visited vs grid resolution G:\n");
int Gs[] = {30,100,300,1000,3000,10000};
long prev = 0; int prevG = 0;
for (int gi=0; gi<6; gi++){
long d = filter_distinct(te, NTE, Gs[gi]);
double dim = (prev && prevG) ? log((double)d/prev)/log((double)Gs[gi]/prevG) : 0.0;
printf(" G=%-6d : %9ld distinct (box-dim slope %.2f)\n", Gs[gi], d, dim);
prev = d; prevG = Gs[gi];
}
printf(" [SNS saturated at ~14; if this KEEPS GROWING with G, the mixed-state set is fractal]\n\n");
free(tr); free(te);
return 0;
}