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?


  • $\begingroup$ 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? $\endgroup$ – 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$.

  • $\begingroup$ What if the serie is infinite, is it then possible to have a and b? or if the series n'th element is calculated by a function which is described by a finite serie of a's and b's? $\endgroup$ – Mathematica Jun 4 '14 at 15:08
  • $\begingroup$ @Mathematica If the series is infinite then I'm not sure how you'd evaluate the expression. Regarding your second question, I'll let you think about it. $\endgroup$ – Yuval Filmus Jun 5 '14 at 3:19
  • $\begingroup$ +1, diagonal argument a-la Turing, however what about the functions add and multiply, dont they produce all (numeric) computable functions (including exponentiation)? $\endgroup$ – Nikos M. Jun 5 '14 at 21:00
  • 1
    $\begingroup$ @NikosM. Perhaps they produce all primitive recursive functions, but certainly not all recursive functions, since there is no effective enumeration of all recursive functions. $\endgroup$ – Yuval Filmus Jun 6 '14 at 0:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.