Hi everyone,
I've been working on a rigorous algebraic framework for Rule 30 , and I'm reaching out to this community to see if we can tackle this: finding a closed-form expression for the automaton's support sets, or formally proving that one cannot exist due to Computational Irreducibility.
The Framework in Brief:
By rotating the coordinates to a one-sided recursion and lifting the Boolean operators (F_2) to integers (Z) via the binomial basis , I've shown that Rule 30 can be evaluated using an exact support-set algebra.
Projecting the integrated integer polynomials back to F_2 using Lucas' Theorem reveals that the evolution of the automaton relies on finite integer support sets, Sm The sequence follows this exact recursion:
Sm=Inc((Sm−1∗Sm−2)ΔSm−1ΔSm−2)
Where the operators are defined as:
- ∗ is a subset OR-convolution
- Δ is the symmetric difference (XOR)
- Inc is a discrete increment operator (adding +1 to every element)
I have successfully mapped these support sets into masked dyadic blocks B(v,M) , which allows for the state of any cell to be queried in strictly bounded O(logn) time. Furthermore, this allows us to bound the 2D spatial rows between the geometric floor (⌊m/2⌋) and a Fibonacci algebraic ceiling (Fm+1)−1.
The main question:
Currently, my evaluation of Sm is heavily recursive, depending directly on the two preceding terms Sm−1 and Sm−2 Is it mathematically possible to find a closed-form, non-recursive expression for Sm as a direct function of m?
Alternatively, can we formally prove that the +1 carry-collisions introduced by the Inc operator permanently shatter these subsets, thereby proving that no such closed-form solution can exist? (This would essentially serve as a direct formalization of Computational Irreducibility for Rule 30) .
I have attached my working paper and a Mathematica notebook that implements the Dyadic Block evaluator and the exact support recursion.
I would deeply appreciate any insights, references, or ideas from the mathematicians and computational theorists here. Could generating functions or advanced lattice theory bypass this recursive step?
Thank you!
Attachments:
