This can be proved by induction. Or you can cite Craig's theorem (the less known one) for that. See [1]
Honestly, I don't see the endgame here.
[1] https://math.stackexchange.com/questions/839926/is-there-a-p...
Consider a computational model that, rather than work by successively rewriting an expression over and over in a way that honors some equivalence relation over expressions, it works by explicitly building the sequence of such expressions. In that kind of system, every computational state properly contains the previous state. Things grow and grow and never get "deleted". Yet such a system can clearly be universal.
I see the endgame now, thanks guys.
In the negative case, it would say the idea doesn't pan out.
In the positive case, it would mean that you can use just S instead of S and K when doing combinator reduction, but doesn't change that this kind of reduction is not super efficient practically speaking.
The Wolfram Foundation ("Wolfram") is offering $20,000 (US) in prize money ("Prize") for a correct solution ("Solution") to the Wolfram S Combinator Challenge ("the Challenge"). The Prize shall go to the first individual or group to successfully submit a Solution, providing a full proof of such Solution to the satisfaction of the prize committee in accordance with these guidelines.
The invitation to participate, and eligibility to win this Prize, is extended to everyone. Each submitter agrees to be bound and abide by the rules, decisions and interpretations of the prize committee.
Submissions will be accepted until a satisfactory Solution has been achieved.
All submissions must be the original work of the submitter(s) and include the names of all relevant contributors. Anonymous submissions will not be accepted.
Submissions remain the property of their submitter(s), but the submitter grants Wolfram the non-exclusive royalty-free right to publish the submission.
Submissions will be judged by the prize committee, and all decisions will be final and binding upon all participants. In the event of unexpected circumstances (such as proofs with different axiomatic foundations), the prize committee will make a discretionary decision consistent with the goals and purpose of the Prize.
The prize committee may request additional or clarifying information in connection with submissions. Submitters will be contacted at the email addresses they provide.
Winners may be required to provide proof of identity, address and birth date, as well as to execute and return tax acknowledgment forms, a liability release and a publicity release prior to claiming the Prize.
By making a submission for the Prize, submitters hereby release and agree to indemnify and hold harmless Wolfram from and against any and all costs, claims or damages, whether due to negligence or otherwise, due in whole or in part, directly or indirectly, for their participation therein.
Note: The Wolfram S Combinator Challenge is a definite, precise problem. Submissions that do not provide definite, precise results and arguments will not be considered.
The Solution should be submitted in the form of a technical research paper, suitable for publication. If successful, the submission will be published.
By uploading a submission, you are agreeing to the Prize guidelines.