Stephen Wolfram's: A New Kind of Science | Online
Jump to Page
Look Up in Index

Chapter 11 Notes > Section 12 > Page 1122 > Note (a) Previous note-----Next note
Notes for: The Notion of Computation | Universality in Turing Machines and Other Systems

*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^n 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].


Page image


Pages related to this note:


All notes on this page:

* Combinators
* Combinator properties
* All notes for this section
* Downloadable programs for this page
* Downloadable images
* Search Forum for this page
* Post a comment
* NKS | Online FAQs
From Stephen Wolfram: A New Kind of Science [citation] Previous note-----Next note