Registered: Jul 2006
Posts: 13

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.

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

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

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

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 6

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

Report this post to a moderator | IP: Logged