[Universality of S-K Combinator] - A New Kind of Science: The NKS ForumA New Kind of Science: The NKS Forum
Pages:1
Universality of S-K Combinator
(Click here to view the original thread with full colors/images)
Posted by: Sean Lynch
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.
Posted by: Jason Cawley
No, it isn't from a search, it is a deliberate construction. See this note -
http://www.wolframscience.com/nksonline/page-1123b-text
Posted by: Matthew Szudzik
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
Forum Sponsored by Wolfram Research
© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. |
Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings