The Wolfram S Combinator Challenge(combinatorprize.org)
combinatorprize.org
The Wolfram S Combinator Challenge
https://www.combinatorprize.org/
23 comments
> S combinator always duplicates its last parameter, never deletes it. That's why K is needed for universality.
This is somewhat covered in the first link of the background, a Modern Introduction to Combinators:
> So how might this work for S combinator expressions? Basically any sophisticated computation has to live on top of an infinite combinator growth process. Or, put another way, the computation has to exist as some kind of “transient” of potentially unbounded length, that in effect “modulates” the infinite growth “carrier”.
> One would set up a program by picking an appropriate combinator expression from the infinite collection that lead to infinite growth. Then the evolution of the combinator expression would “run” the program. And one would use some computationally bounded process (perhaps a bounded version of a tree automaton) to identify when the result of the computation is ready—and one would “read it out” by using some computationally bounded “decoder”.
I understand it as "you don't need the S combinator application sequence to halt for it to compute something".
This is somewhat covered in the first link of the background, a Modern Introduction to Combinators:
> So how might this work for S combinator expressions? Basically any sophisticated computation has to live on top of an infinite combinator growth process. Or, put another way, the computation has to exist as some kind of “transient” of potentially unbounded length, that in effect “modulates” the infinite growth “carrier”.
> One would set up a program by picking an appropriate combinator expression from the infinite collection that lead to infinite growth. Then the evolution of the combinator expression would “run” the program. And one would use some computationally bounded process (perhaps a bounded version of a tree automaton) to identify when the result of the computation is ready—and one would “read it out” by using some computationally bounded “decoder”.
I understand it as "you don't need the S combinator application sequence to halt for it to compute something".
[deleted]
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.
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.
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.
An implicit K suffices for universality, as in \x\y\z. x z (y (\w.z))
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.
cvoss, ezwoodland, tromp and v64 made a good point. As v64 points I was thinking of a Combinatory Completeness not Turing Completeness. Dropping that requirement as cvoss, ezwoodland, tromp point you can simulate deletion (that's what quantum computing does btw see No-deleting theorem).
I see the endgame now, thanks guys.
I see the endgame now, thanks guys.
Barendregt & Manzonetto's 2022 "A lambda calculus satellite" has a whole chapter on the S fragment, for those interested
> 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.
I wonder how long in advance Stephen Wolfram first had this thought and waited until the centennial to publicize the suggestion.
I’ve talked with him in person for a couple of hours once and he was the most endearing kind of grandfatherly person. Really caught me off guard how pleasant and open he was. Somehow I was expecting someone a lot more adversarial.
Wait wouldn't this revolutionize computing? Seems like a rather low bounty for such a monumental proof
No? Why would it?
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.
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.
I was thinking in specifically the positive, would compression or encoding potentially allow for more compact representation of programs. Like Kolmogorovs
No not really. It's a thing you can do just because you can, like writing a book without the letter "e". Closer to the context of computation, it's like building a computer using only NAND gates. Or, given how restrictive the S combinator supposedly is, using only AND and OR gates. It won't make an efficient computer because your design is convoluted to all hell to make up for your choice to never use a NOT gate. Even the one made from NAND isn't efficient, because even though NAND can make any circuit without being too convoluted, it's not the most efficient way to make all circuits.
If anything, this would be a less compact representation.
The site doesn’t open from Ukraine. Any suggestion?
Does this mean that internet blocking by third parties is above any science? How will researchers be able to make discoveries if every scientific website gets blocked? Many mysteries of the universe could end up blocked by a dumb firewall. Please do something with this.
Needs a (2021)
More wolf-slop.
I 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.
Someone having met Epstein is about as interesting and concerning as having met Theodore McCarrick [1] or Harvey Weinstein [2].
Those kind of people aren't cartoon villains who only meet with people as part of their villainous activities.
The vast majority of people they meet with are for their other activities and interests. Most people meeting with McCarrick for example were meeting for the reasons they would meet with any Archbishop (or priest or bishop, depending on when they met him), or met with him for some other mutual, legal, interest or business reason.
Same with Weinstein. Most people he met would be meeting for the same reason they would meet any producer, or for some other mutual, legal, interest of business reason.
And same with Epstein. Epstein fancied himself as a patron of the sciences and made contact with a lot of scientists over their research and possible funding of their labs. He also fancied himself a philanthropist and had many contacts related to that.
[1] Former Archbishop of Newark and of Washington.
[2] One of the biggest and most successful Hollywood movie producers.
Those kind of people aren't cartoon villains who only meet with people as part of their villainous activities.
The vast majority of people they meet with are for their other activities and interests. Most people meeting with McCarrick for example were meeting for the reasons they would meet with any Archbishop (or priest or bishop, depending on when they met him), or met with him for some other mutual, legal, interest or business reason.
Same with Weinstein. Most people he met would be meeting for the same reason they would meet any producer, or for some other mutual, legal, interest of business reason.
And same with Epstein. Epstein fancied himself as a patron of the sciences and made contact with a lot of scientists over their research and possible funding of their labs. He also fancied himself a philanthropist and had many contacts related to that.
[1] Former Archbishop of Newark and of Washington.
[2] One of the biggest and most successful Hollywood movie producers.
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...