In earlier posts, I described Coherence Filters as rules that carve stable patterns out of the Chaos Reservoir. Every filter is itself a pattern in Chaos. Here I will make that precise by showing how coherence filters can be encoded as binary strings, with explicit operational semantics.
Universal, Prefix-Free Setup
Fix a universal prefix-free Turing machine UU.
All integers are encoded with Elias gamma (prefix-free).
A program (filter code) is a concatenation of self-delimiting fields. When a field includes a raw bitstring, we precede it with its gamma-encoded length.
A 2-bit type tag tells UU which semantics to use:
TYPE=1: Π “forbid substring” filters.
TYPE=2: Martin-Löf style randomness tests.
Each finite code corresponds to a clopen cylinder1 of reals. Every real with that prefix encodes the same filter. This makes filters literally patterns in Chaos.
TYPE 1 — Π Filters: Forbid a Substring
Program layout:
Semantics:
U(p) enumerates all finite strings containing forbidden block b.
The filter Fb is the set of infinite sequences with no occurrence of b.
Example: forbid b=0000.
γ(1)=10, γ(4)=111000.
Program bits:
101110000000(12 bits).Meaning: the real interval [0.101110000000, 0.101110000000 + 2^-12) all encode the filter “no 0000.”
This yields an effectively closed subset of Cantor space.
TYPE 2 — Martin-Löf Style Filters
Program layout:
Semantics:
U(p) enumerates a Martin-Löf test (Un).
For each n, it enumerates all compressible strings of length n (program length < n-m).
The filter F(m) is the set of sequences that pass the test, i.e. not in infinitely many Un.
Example: set m=10.
γ(2)=1100, γ(10)=11110010.
Program bits:
110011110010(12 bits).Meaning: all reals with that prefix encode the filter F(10), which enforces complexity bounds on prefixes.
This yields a randomness-style typicality constraint.
Why This Matters
Each coherence filter is a finite prefix-free bitstring: a pattern in Chaos.
Complexity K(F) = length of the shortest code.
Selectivity measured by Lebesgue measure (for Π) or by m (for ML tests).
Filters compose: conjunction by concatenating codes and running both recognizers, disjunction by allowing either to accept.
Conclusion
Encoding coherence filters as binary strings makes the recursion clear: every filter is a pattern in Chaos. Their complexity, selectivity, and composition can be studied directly in algorithmic information terms. This gives us a rigorous way to move from Chaos → Coherence → Constructors with explicit encodings.
A clopen cylinder in Cantor space is the set of all infinite sequences that begin with a given finite binary prefix. Such sets are both open (they contain all extensions of that prefix) and closed (their complement is a union of other such cylinders). Each finite program prefix in our encoding corresponds to one of these cylinders, meaning that an uncountable collection of reals encodes the same coherence filter.