Combinator properties

The size of a combinator expression is conveniently measured by its LeafCount. If the evolution of a combinator expression reaches a fixed point, then the expression generated is always the same (Church–Rosser property). But the behavior in the course of the evolution can depend on how the combinator rules are applied; here expr /. crules is used at each step, as in the symbolic systems of page 896. The total number of combinator expressions of successively greater sizes is {2, 4, 16, 80, 448, 2688, 16896, 109824, …} (or in general 2ⁿ Binomial[2n - 2, n - 1]/n; see page 897). Of these, {2, 4, 12, 40, 144, 544, 2128, 8544, …} are themselves fixed points. Of combinator expressions up to size 6 all evolve to fixed points, in at most {1, 1, 2, 3, 4, 7} steps respectively (compare case (a)); the largest fixed points have sizes {1, 2, 3, 4, 6, 10} (compare case (b)). At size 7, all but 2 of the 16,896 possible combinator expressions evolve to fixed points, in at most 12 steps (case (c)). The largest fixed point has size 41 (case (d)). s[s[s]][s][s][s][s] (case (e)) and s[s][s][s[s]][s][s] lead to expressions that grow like 2^t/2. The maximum number of levels in these expressions (see page 897) grows roughly linearly, although Depth[expr] reaches 14 after 26 and 25 steps, then stays there. At size 8, out of all 109,824 combinator expressions it appears that 49 show exponential growth, and many more show roughly linear growth. s[s][k][s[s[s]][s]][s] goes to a fixed point of size 80. s[s[s]][s][s][s][s[k]] (case (i)) increases rapidly to size 7050 but then repeats with period 3. s[s[s[s][s]]][s][s][k] (case (j)) grows to a maximum size of 1263, but then after 98 steps evolves to a fixed point of size 17. For s[s][k][s[s[s][k]]][k] (case (k)) the size at step t - 7 is given by

h[1] = h[2] = h[3] = 12

h[t_] := If[Mod[t, 4]  2, 2, 1] (h[Ceiling[t/2] - 1] + t) + {3, 5, -7, -1}〚Mod[t, 4] + 1〛

Examples with similar behavior are s[s[s][k]][s][s[s][k]], s[s[s]][s][s[s][k]][k] and s[s[s][s]][s][s[s][k]]. Among those with roughly exponential growth but seemingly random fluctuations are s[s[s[s]]][s][s][s][k], s[s[s]][s][s[s][s]][k] and s[s[s[s]][s][s]][k][s].