Return to Answer

• (Restricted) Unlambda is Turing-complete, so I can build an Unlambda function for any computable function in $C_M$.
• I can build a constant function whose value is the representation of that Unlambda function using $h$, $s$, and $k$. For example, for add1 = `s``s`ksk, I can build $h(s,h(h(s,h(k,s)),k))$ whose constant value is $3212212010_4 = 944516$
• I can build a function that evaluates any function $f$ built by the above process on $\mathbb{N}$, simply as $h(f,init)$.

• Unlambda (restricted to s and k) is Turing-complete, so I can build a (restricted) Unlambda function for any computable function in $C_M$.
• I can build a constant function whose value is the representation of that Unlambda function using $s$, $k$ and $(\cdot)$. For example, for add1 = `s``s`ksk, I can build $s\cdot((s\cdot(k\cdot s))\cdot k)$ whose constant value is $2\cdot3212212010_4+1 = 1889033$
• I can build a function that evaluates any function $f$ built by the above process on $\mathbb{N}$, simply as $f \cdot init$.

Now that I've talked about the programming language, let's see how to interpret it, and whether or not this interpretation is easily computable. It turns out that one can easily build a model of Unlambda (excepted its more complex operators, such as I/O) from any model of the untyped lambda calculus by letting $[\![k]\!] = [\![(\lambda x.(\lambda y.x))]\!]$, $[\![s]\!] = [\![(\lambda x.(\lambda y.(\lambda z.(x z (yz))]\!]$, and $[\![`XY]\!] = [\![X]\!] [\![Y]\!]$.

Now that I've introduced the programming language, which is the most interesting part and the crux of this answer, let's go through the tedious details of how to use it to formally answer your question.

• First define an embedding $\phi$ of unlambda programs (restricted to s and k) into the natural numbers. We could use base-4 encoding by mapping its alphabet $\Sigma = \{\text{k}, \text{s}, \text{`}, \text{^}\}$ with $\{0, 1, 2, 3\}$ ($\text{^}$ is the start-of-string character). So for example $\phi(k) = \phi(\text{^k}) = 30_4 = 12$, and $\phi(i) = \phi(\text{^``skk}) = 322100_4 = 3728$.
• We can then define $\phi^{-1}$ as the opposite operation, except that for convenience, we'll remove the starting $\text{^}$. So $\phi^{-1}(12) = \text{k}$
• Let's also define an unlambda evaluation function $\text{uneval}$, partially defined on $\mathbb{N}\times\mathbb{N}$ and mapping to $\mathbb{N}$. For any $p$, $q$, $\text{uneval}(p,q)$ is defined as the number of stars printed when compiling and running $\text{``}||\phi^{-1}(p)||church(q)||.*$ as an Unlambda program, where $church(q)$ is the representation of the $q$-th church numeral in Unlambda, $.*$ is the Unlambda function which prints one star, and $||$ represents string concatenation. If the Unlambda program thus defined doesn't compile or never halts, then $\text{uneval}$ isn't defined on $(p,q)$.
• Then define the following functions
  • $k : \mathbb{N} \to \mathbb{N}, n \mapsto 2\phi(\text{^k})+1 = 25$
  • $s : \mathbb{N} \to \mathbb{N}, n \mapsto 2\phi(\text{^s})+1 = 27$
  • $init : \mathbb{N} \to \mathbb{N}, n \mapsto 2n$
• Let $B = \{k, s, init\}$
• Define $h : \mathbb{N}\times\mathbb{N} \to \mathbb{N}$ as follows
  • $h(2p, n)$ is undefined
  • $h(2p+1,2q+1) = 2\phi(\text{^`}||\phi^{-1}(p)||\phi^{-1}(q))+1$, if $\phi^{-1}$ is defined on $p$ and $q$, and undefined otherwise
  • $h(2p+1,2q) = \text{uneval}(p,q)$, if $\text{uneval}$ is defined on $(p,q)$
• Define $(\cdot)$ as $(f\cdot g)(n) = h(f(n),g(n))$.

Using these definitions, we have

• $h \in C_M$, because $\phi$, $\phi^{-1}$, $||$, $\text{uneval}$ and basic arithmetic are all computable.
• and $\forall f,g \in C_M : \forall x \in \mathbb{N} : (f\cdot g)(x) = h(f(x), g(x))$, by definition of $(\cdot)$

Finally, $(B, \cdot)$ generates $C_M$ entirely, because

• (Restricted) Unlambda is Turing-complete, so I can build an Unlambda function for any computable function in $C_M$.
• I can build a constant function whose value is the representation of that Unlambda function using $h$, $s$, and $k$. For example, for add1 = `s``s`ksk, I can build $h(s,h(h(s,h(k,s)),k))$ whose constant value is $3212212010_4 = 944516$
• I can build a function that evaluates any function $f$ built by the above process on $\mathbb{N}$, simply as $h(f,init)$.

Unlambda is an example of a Turing-complete programming language that implements your requirements.

• Unlambda has only one type, functions. They are also its only basic syntactic elements. In particular there are no variables.
• Its expressive power only requires two base terms, s, and k. They would be your base $B$. k takes two arguments and returns the first, while s takes three arguments, and applies the result of applying the first one to the third one, to the result of applying the second one to the third one.
• It has an additional construct, `, which represents function application. It would be your binary operator $(\cdot)$. It is written in a prefix manner.
• So for any term X, Y and Z we have ``kXY = X, and ```sXYZ = ``XZ`YZ. These simple rules, believe it or not, are sufficient to make Unlambda Turing-complete.
• Unlambda has a few more built-ins but they are just here to make the programmer's life easier (although mentioning easy anywhere in the context of this language is probably an overstatement).

Natural numbers can be represented using Church's method, e.g. $3$ can be written as ``s``s`ksk``s``s`kski (note i, the identity, can be written as ``skk). Pretty simple, no? Recursion can be defined by building a fixed point combinator, and from there the usual techniques can be applied to define more and more complex functions until an universal Turing machine has been simulated.

This language is based on SKI combinator calculus, which itself finds its source in Combinatory Logic. There is a simple mapping between the Lambda and SKI calculi, which luckily makes proving Turing completeness much easier than actually doing the work!

Of course, I've really only talked about a programming language, which is an abstract syntactic construct (even if I find it more fun). To really answer your question, I should note that there exists a model of Unlambda in $C_M$ (I/O extensions excepted). Indeed it is easy to build such a model from any model of the untyped lambda calculus by letting $[\![k]\!] = [\![(\lambda x.(\lambda y.x))]\!]$, $[\![s]\!] = [\![(\lambda x.(\lambda y.(\lambda z.(x z (yz))]\!]$, and $[\![`XY]\!] = [\![X]\!] [\![Y]\!]$.

Unlambda is an example of a Turing-complete programming language that implements your requirements.

• Unlambda has only one type, functions. They are also its only basic syntactic elements. In particular there are no variables.
• Its expressive power only requires two base terms, s, and k. They would be your base $B$. k takes two arguments and returns the first, while s takes three arguments, and applies the result of applying the first one to the third one, to the result of applying the second one to the third one.
• It has an additional construct, `, which represents function application. It would be your binary operator $(\cdot)$. It is written in a prefix manner.
• So for any term X, Y and Z we have ``kXY = X, and ```sXYZ = ``XZ`YZ. These simple rules, believe it or not, are sufficient to make Unlambda Turing-complete.
• Unlambda has a few more built-ins but they are just here to make the programmer's life easier (although mentioning easy anywhere in the context of this language is probably an overstatement).

Natural numbers can be represented using Church's method, e.g. $3$ can be written as ``s``s`ksk``s``s`kski (note i, the identity, can be written as ``skk). Pretty simple, no? Recursion can be defined by building a fixed point combinator, and from there the usual techniques can be applied to define more and more complex functions until an universal Turing machine has been simulated.

This language is based on SKI combinator calculus, which itself finds its source in Combinatory Logic. There is a simple mapping between the Lambda and SKI calculi, which luckily makes proving Turing completeness much easier than actually doing the work!

Now that I've talked about the programming language, let's see how to interpret it, and whether or not this interpretation is easily computable. It turns out that one can easily build a model of Unlambda (excepted its more complex operators, such as I/O) from any model of the untyped lambda calculus by letting $[\![k]\!] = [\![(\lambda x.(\lambda y.x))]\!]$, $[\![s]\!] = [\![(\lambda x.(\lambda y.(\lambda z.(x z (yz))]\!]$, and $[\![`XY]\!] = [\![X]\!] [\![Y]\!]$.