A New Kind of Science: The NKS Forum (http://forum.wolframscience.com/index.php)
- Pure NKS (http://forum.wolframscience.com/forumdisplay.php?forumid=3)
-- Universality of S-K Combinator (http://forum.wolframscience.com/showthread.php?threadid=1157)

Universality of S-K Combinator

On page 713 it is shown that combinators are universal by giving an expression that will reproduce successive steps of rule 110.

I was wondering if anyone knows how that particular expression was found. I'm assuming it was some type of systematic search but exactly how one would go about finding such an expression is not clear to me.

No, it isn't from a search, it is a deliberate construction. See this note -

http://www.wolframscience.com/nksonline/page-1123b-text

No, I constructed that expression myself, under the direction of Stephen Wolfram. I wrote a cellular automaton emulator in the language of Lambda Calculus, and then converted it to s-k combinators using the algorithm ToC on page 1122 of NKS.

See the code at the end of the chapter 11 book code, on Cellular automaton combinators. You can use the "downloadable programs from this section" link on the right side of this page, for example - 1123