Combinators for the Primitive Recursive Functions It is well-known that the S and K combinators are Turing Complete. Are there combinators that suffice to yield (only) the primitive recursive functions?
Yes, but you have to consider typed combinators. That is, you need to give $S$ and $K$ 
the following type schemas:
$$
\begin{array}{lcl}
K &amp; : &amp; A \to B \to A \\
S &amp; : &amp; (A \to B \to C) \to (A \to B) \to (A \to C)
\end{array}
$$
where $A, B$, and $C$ are meta-variables which can be instantiated to any concrete type at each use. 

Then, you want to add the type $\mathbb{N}$ of natural numbers to the language of types, and add the following combinators: 
$$
\begin{array}{lcl}
z &amp; : &amp; \mathbb{N} \\ 
succ &amp; : &amp; \mathbb{N} \to \mathbb{N} \\ 
iter &amp; : &amp; \mathbb{N} \to (\mathbb{N} \to \mathbb{N}) \to \mathbb{N} \to \mathbb{N}
\end{array}
$$ 

The equality rules for the additions are:
$$
\begin{array}{lcl}
iter\;i\;f\;z &amp; = &amp; i \\
iter\;i\;f\;(succ\;e) &amp; = &amp; f(iter\;i\;f\;e)
\end{array}
$$ 

It's much easier to read the programs you write, if you just write programs in the simply-typed lambda calculus, augmented with the numerals and iteration. The system I've described is a restriction of Goedel's T, the language of higher-type arithmetic. In Goedel's T, the typing for iteration is less limited:
$$
\begin{array}{lcl}
iter &amp; : &amp; A \to (A \to A) \to \mathbb{N} \to A
\end{array}
$$ 
In T, you can instantiate $iter$ at any type, not just the type of natural numbers. This takes you past primitive recursion, and lets you define things like Ackerman's function.  

EDIT: Xoff asked how to encode the predecessor function. It follows via a standard trick. To explain, I'll use lambda-notation for this (which can be eliminated with bracket-abstraction), since that's far more readable. First, assume that we have pairs and the more general type for $\mathit{iter}$. Then, we can define:

$$
\begin{array}{lcl}
pred' &amp; = &amp; \lambda k.\;iter \;(z, z) \; (\lambda (n, n').\; (succ\;n, n))\;k\\
pred  &amp; = &amp; \lambda k.\;snd(pred'\;k)
\end{array}
$$ 

If you just have the nat-type iterator, then you need to exploit the isomorphism that $\mathbb{N} \simeq \mathbb{N} \times \mathbb{N}$, which is annoying but poses no fundamental obstacle.