logoalt Hacker News

The Wolfram S Combinator Challenge

76 pointsby paraschopralast Monday at 8:39 AM21 commentsview on HN

Comments

jmjyesterday at 8:10 PM

S 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...

show 6 replies
fritzoyesterday at 8:19 PM

Barendregt & Manzonetto's 2022 "A lambda calculus satellite" has a whole chapter on the S fragment, for those interested

divbzeroyesterday at 10:26 PM

> The S, K combinators defined by Moses Schönfinkel on December 7, 1920, are together known to be computation universal. On December 7, 2020, Stephen Wolfram made the suggestion that S alone might also be universal.

I wonder how long in advance Stephen Wolfram first had this thought and waited until the centennial to publicize the suggestion.

show 1 reply
bingobangobungoyesterday at 9:18 PM

Wait wouldn't this revolutionize computing? Seems like a rather low bounty for such a monumental proof

show 1 reply
bryan0yesterday at 10:32 PM

Needs a (2021)

ellis0nyesterday at 10:29 PM

The site doesn’t open from Ukraine. Any suggestion?

show 1 reply
browningstreetyesterday at 7:58 PM

I think that website cost more than the listed prize amount.

show 1 reply
KnuthIsGodyesterday at 9:12 PM

More wolf-slop.