Comment by jmj

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.

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

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.

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.

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.

An implicit K suffices for universality, as in \x\y\z. x z (y (\w.z))