Stephen Wolfram traces the history of combinators in Combinators: A Centennial View. Wolfram says in the associated lifestream event, Combinators: A 100-Year Celebration, that he has been interested in combinators for a long time and gives an indication of the historical arc of combinators and how they relate to other things.
Stephen Wolfram writes in Announcing the S Combinator Challenge that:
In the usual S, K combinator setup one does computations by setting up an initial combinator expression that encodes the computation one wants to do… Of course, not all computations halt, and for computations that don’t halt, no fixed point will ever be reached.
—Stephen Wolfram https://writings.stephenwolfram.com/2021/06/1920-2020-and-a-20000-prize-announcing-the-s-combinator-challenge/
With the S combinator alone a direct input → output representation of computations won’t work. The reason is … that halting S combinator evolutions don’t have enough richness to represent arbitrary computations.
Related post:
Stephen Wolfram on Computational Irreducibility
Leave a Reply
You must be logged in to post a comment.