Notes

Chapter 11: The Notion of Computation

Section 12: Universality in Turing Machines and Other Systems


Single [universal] combinators

As already noted by Moses Schönfinkel in 1920, it is possible to set up combinator systems with just a single combinator. In such cases, combinator expressions can be viewed as binary trees without labels, equivalent to balanced strings of parentheses (see page 989) or sequences of 0's and 1's. One example of a single combinator system can be found using {s -> j[j], k -> j[j[j]]}, and has combinator rules (whose order matters):

{ j[j][x_][y_][z_] -> x[z][y[z]], j[j[j]][x_][y_] -> x}

The smallest initial conditions in this case that lead to unbounded growth are of size 14; two are versions of those for s, k combinators above, while the third is j[j][j[j]][j[j]][j[j][j[j][j]]][j[j][j]].

The forms j[j] and j[j[j]] appear to be the simplest that can be used for s and k; j and j[j], for example, do not work.


From Stephen Wolfram: A New Kind of Science [citation]