Decomposition of the set of computable functions into base functions

Question

Say I have some computation model/programming language $M$ (e.g. Turing machine or equivalent), and let $C_M$ be the set of all partial or total functions $f : \mathbb{N} \to \mathbb{N}$ computable by that model. Also, assume that $C_M$ is countable.

Now let $B = \{ B_1, B_2, ... , B_n \}$ a finite set of computable base functions and $\cdot : C_M \times C_M \to C_M$ an binary operator, which serves as a combination function. Thus, $(B,\cdot)$ is a magma.

I can now choose $B$ and $\cdot$ in such a way that I can decompose each computable function $f \in C_M$ into a finite product from $(B,\cdot)$, i.e. $\forall f \in C_M : \exists b_1, b_2, ..., b_k \in B : f = b_1 \cdot b_2 \cdot ... \cdot b_k$.

To show that, I consider that my programming language consists of a set of instructions $I$ and programs are words over $I$. Then, I choose exaclty one base function $b_{i,m}$ for each instruction $i_m$. Because each computable function $f$ has at least one program computing it, I can just pick one of those $f$-computing programs $P_f \in I^*$ and define $b_{i,a} \cdot b_{i,b} \cdot b_{i,c} ... = f$ when the program is the word $P_f = i_a i_b i_c ...$.

This decomposition is obviously not very useful, because it makes the base vectors arbitrary and the definition of $\cdot$ an infinite list of special cases. To consider it useful, the operator $\cdot$ should have some form of structure/finite definition, or in other words, be computable. My interest would be an element-wise function, so that given two values $f(x)$ and $g(x)$, it should be possible to compute $(f\cdot g)(x)$.

My question: Assuming $M$ is turing-complete, is it possible to choose $(B,\cdot)$ in such a way that $\cdot$ is elementwise computable, i.e.

$\exists h \in C_M : \forall f,g \in C_M : \forall x \in \mathbb{N} : (f\cdot g)(x) = h(f(x), g(x))$

and still have each computable function being decomposable into a finite product from $(B,\cdot)$?

Answer 1

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

• 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$.