For mathematicians
Rule 30, Collatz and Mahler's 3/2, technically
The three problems share one skeleton: a free side that is a full shift, a constrained side that is a thin language, and the requirement that they agree for ever. This page states that correspondence with the definitions and the theorems it rests on, and says exactly where each problem is open. It is a calibration, not a route.
Rule 30, period two
Setting. Column 0 held to x(0, t) = t mod 2 from time 0; column 1 the trace c; the left half-plane a function of (wall, trace) by left permutivity. The free side is the left half at the wall: by permutivity the map from a left half (at time 0) to its itinerary against the wall is a bijection, so the left side is a full shift (RULE30-PRIZE.md 8.39, WA1). The constrained side is the visible language L of real traces: factorial, of positive entropy, with growth rate at most 20.1236 per visible bit (the channel bound, certified at width 28). The object is a finite configuration whose coupled orbit keeps the wall for ever. Sparsity: the entropy squeeze bounds the number of width-w configurations keeping the wall for T steps by 2w − αT in measurement, with the left part's share proved (8.33, 8.51). Emptiness is proved when every admissible column 1 is eventually periodic (Jen) or monotone (Condrey), and when column 1 is Sturmian (Theorem E). Open for the real column 1, which is a kicked rotation of positive entropy.
Collatz
Setting. T(n) = n/2 for even n, (3n+1)/2 for odd n; the parity sequence of n. The free side: the first w − 1 parities of a w-bit n are a bijection with n mod 2w−1 (Terras 1976), so the parity prefix is a full shift. The constrained side: after k steps, Tk(2k m + r) = 3a m + Tk(r) with 0 ≤ Tk(r) < 3a, where a is the number of odd steps (the least-residue lemma; Terras, Lagarias 1985), so the state after the free bits is a residue modulo a power of 3 and the question is about its binary digits. The object: an orbit that never falls below its start. Sparsity: almost every orbit attains a value below any fixed function tending to infinity (Tao 2019); the count of w-bit starts staying above their start for T steps follows Terras's coin past the free bits with an excess at most 3.7 bits to w = 30 (COLLATZ-PRIZE.md 1). Emptiness is proved for periodic and Sturmian parity sequences by the window principle: a block of the parity sequence can repeat only if it is no longer than the state is large, giving complexity at least 1.71 n for an infinite orbit (Dubickas 2009, Theorem 5) and no rational with a Sturmian parity sequence. Open for every single orbit as opposed to almost all.
Mahler's 3/2 problem
Setting. ξ > 0 is a Z-number if {ξ (3/2)n} < 1/2 for every n ≥ 0 (Mahler 1968). The free side: the integer parts of ξ (p/q)n form a full shift, every itinerary realised once by residues modulo qk. The constrained side: the fractional parts follow a linear mod-one map whose admissible strings in a short interval are few. The object: a ξ whose two itineraries agree for ever. Sparsity: the Z-numbers below x number at most xγ for some γ < 1 (Flatto, Lagarias, Pollington 1995, Theorem 1.1); more generally the fractional parts of ξ (p/q)n cannot all lie in an interval shorter than 1/p. Emptiness is proved when only finitely many fractional orbits are admissible (FLP Theorem 3.2): pigeonhole makes the coupled orbit periodic and the free side's injectivity forbids it. Open for the interval of length 1/2, where infinitely many orbits are admissible. Kari and Kopra restate the problem as a question about one column of the cellular automaton that multiplies by p/q in base pq, which puts it in the same class of rapidly left-expansive automata as Rule 30; their partial result (Theorem 4.9) excludes some finite unions of intervals, non-constructively.
The correspondence and its limits
| Ingredient | Rule 30, period two | Collatz | Mahler's 3/2 |
|---|---|---|---|
| Free side (full shift) | left half at the wall | parity prefix ↔ n mod 2w−1 | integer parts, residues mod qk |
| Constrained side | visible language L, rate ≤ 0.1236 bits | residue mod 3a after the free bits | fractional orbits in an interval |
| Sparsity theorem | entropy squeeze (measured; left part proved) | Tao 2019 (almost all); Terras's coin | FLP 1995, ≤ xγ |
| Emptiness theorem | Jen 1990; Condrey 2026; Theorem E | window principle; Dubickas 2009 | FLP Theorem 3.2 |
| Where it stops | column 1 of positive entropy | a single orbit | infinitely many admissible orbits |
The common mechanism is exact: a finite constrained side plus an injective free side gives periodicity and a contradiction; a constrained side with infinitely many behaviours gives nothing. The common gap is also exact: every sparsity theorem is a statement about sets (measure, counting, almost all), and each prize is a statement about one object. No theorem surveyed in biology, physics, ergodic theory, automata or computing crosses that gap except by finiteness or by an extremal argument on a single trajectory (RULE30-PRIZE.md 8.47).
Two differences bound the analogy. Collatz's constrained state is an explicit integer, open to arithmetic and exponential sums; Rule 30's is a word in a language, open to automata and combinatorics on words, which is why the Rule 30 record holds exact image automata and certified forbidden words. And Mahler's ξ is a real number, so counting Z-numbers is counting reals in an interval, while Rule 30's object is a finite configuration, countable, and the counting form is a bound on finitely many cases at each width.
Sources. RULE30-PRIZE.md sections 8.33, 8.39, 8.45, 8.47, 8.51, 8.55, 8.58, 8.20; COLLATZ-PRIZE.md honest summary and sections 1 to 5; PRIOR-ART.md entries for Jen 1990, Condrey 2026, Kopra 2021, Kari and Kopra, Flatto–Lagarias–Pollington 1995, Terras 1976, Lagarias 1985, Dubickas 2009, Tao 2019, Yolcu–Aaronson–Heule.