1920, 2020 and a $20,000 Prize: Announcing the S Combinator Challenge—Stephen Wolfram Writings

submited by

Style Pass

2021-06-09 05:00:14

On December 7, 1920, Moses Schönfinkel introduced the S and K combinators—and in doing so provided the first explicit example of a system capable of what we now call universal computation. A hundred years later—as I prepared to celebrate the centenary of combinators—I decided it was time to try using modern computational methods to see what we could now learn about combinators. And in doing this, I got a surprise.

It’s already remarkable that S and K yield universal computation. But from my explorations I began to think that something even more remarkable might be true, and that in fact S alone might be sufficient to achieve universal computation. Or in other words, that just applying the rule

I don’t know for sure that this is true, though I’ve amassed empirical evidence that seems to point in this direction. And today I’m announcing a prize of $20,000 (yes, the “20” goes with the 1920 invention of combinators, and the 2020 making of my conjecture) for proving—or disproving—that the S combinator alone can support universal computation.

Why is it important to know? Obviously it’ll be neat if it turns out that hiding in plain sight for a century has been an even simpler basis for universal computation than we ever knew. But more than that, determining whether the S combinator alone is universal will provide an important additional data point in the effort to map out just where the threshold of universal computation lies.