The Wolfram S Combinator Challenge
combinatorprize.org
The Wolfram S Combinator Challenge
1–10 of 24 posts
Re: The Wolfram S Combinator Challenge
#2I think that website cost more than the listed prize amount.
Re: The Wolfram S Combinator Challenge
#3S combinator always duplicates its last parameter, never deletes it. That's why K is needed for universality.
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...
Re: The Wolfram S Combinator Challenge
#4S combinator always duplicates its last parameter, never deletes it. That's why K is needed for universality. 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...
[deleted]
Re: The Wolfram S Combinator Challenge
#5Barendregt & Manzonetto's 2022 "A lambda calculus satellite" has a whole chapter on the S fragment, for those interested
Re: The Wolfram S Combinator Challenge
#6I think that website cost more than the listed prize amount.
Coincidental timing for Wolfram to pop up here just as it becomes clearer that he might actually have met Epstein after all.
Re: The Wolfram S Combinator Challenge
#7S combinator always duplicates its last parameter, never deletes it. That's why K is needed for universality. 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...
I don't follow your argument. Why must we have the ability to "delete" sub-expressions?
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.
Re: The Wolfram S Combinator Challenge
#8S combinator always duplicates its last parameter, never deletes it. That's why K is needed for universality. 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...
That doesn't matter.
You could imagine a system that accumulates two terms: (actual result, junk). Instead of deleting something it just adds it to the junk part of the pair.
Maybe the junk part itself has computation which never ends, but it doesn't matter because you just extract your result from the left part of the pair.
Re: The Wolfram S Combinator Challenge
#9S combinator always duplicates its last parameter, never deletes it. That's why K is needed for universality. 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...
An implicit K suffices for universality, as in \x\y\z. x z (y (\w.z))
Re: The Wolfram S Combinator Challenge
#10S combinator always duplicates its last parameter, never deletes it. That's why K is needed for universality. 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...
as far as I understand it, turing completeness is a weaker property than combinatory completeness, which Craig's theorem is addressing. The nonexistence of a singleton combinatory basis doesn't necessarily imply the nonexistence of a turing complete combinator.