wolframscience.com

A New Kind of Science: The NKS Forum : Powered by vBulletin version 2.3.0 A New Kind of Science: The NKS Forum > Pure NKS > Universality of S-K Combinator
  Last Thread   Next Thread
Author
Thread Post New Thread    Post A Reply
Sean Lynch
Rowan University
New Jersey

Registered: Jul 2006
Posts: 13

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.

Report this post to a moderator | IP: Logged

Old Post 07-18-2006 05:21 AM
Sean Lynch is offline Click Here to See the Profile for Sean Lynch Click here to Send Sean Lynch a Private Message Click Here to Email Sean Lynch Edit/Delete Message Reply w/Quote
Jason Cawley
Wolfram Science Group
Phoenix, AZ USA

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

Old Post 07-18-2006 02:46 PM
Jason Cawley is offline Click Here to See the Profile for Jason Cawley Click here to Send Jason Cawley a Private Message Edit/Delete Message Reply w/Quote
Matthew Szudzik


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

Old Post 07-18-2006 03:44 PM
Matthew Szudzik is offline Click Here to See the Profile for Matthew Szudzik Click here to Send Matthew Szudzik a Private Message Click Here to Email Matthew Szudzik Edit/Delete Message Reply w/Quote
Post New Thread    Post A Reply
  Last Thread   Next Thread
Show Printable Version | Email this Page | Subscribe to this Thread


 

wolframscience.com  |  wolfram atlas  |  NKS online  |  web resources  |  contact us

Forum Sponsored by Wolfram Research

© 2004-14 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer | Archives