# Two functions which can create any computable function by composing?

Do there exist two computable functions, a and b, which can construct every computable function by a finite serie of a's and b's which is function composed? Fx. let's take the serie, a,b,a,b,b,a,a,a , which function composed is the function, a∘b∘a∘b∘b∘a∘a∘a ( =a(b(a(b(b(a(a(a(x)))))))) ), this function is the function described by the serie, a,b,a,b,b,a,a,a. And I want to know if every program can be described, by such serie.

If such functions exist, can you tell a example of a and b?

Thanks.

• What do you think? What have you tried, and where did you get stuck? In what context did you run into this problem, or what's the practical motivation? – D.W. Jun 4 '14 at 16:00

If such functions existed, they would constitute a computable enumeration of all computable functions, which is impossible for the following reason. Suppose you had a computable enumeration $f_i$ of all computable functions. The function $g\colon i \mapsto f_i(i) + 1$ is then computable, but by definition $g \neq f_i$ for all $i$.