← Back to context

Comment by wasabi991011

11 hours ago

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