$f,g_1,...,g_k$ computable imply $h(x_1,...,x_n)=f(g_1(x_1,...,x_n),...,g_k(x_1,..,x_n))$ computable. Does the converse hold?

76 Views Asked by At

In the book "Computability, complexity and languages" by Davis, Sigal and Weyuker, the following

$\bf THEOREM$

If $f,g_1,...,g_k$ are computable functions, then $h(x_1,...,x_n)=f(g_1(x_1,...,x_n),...,g_k(x_1,..,x_n))$ is computable.

Is stated and proved. I'm interested in knowing if the converse is true, that is, given a computable composition, if each individual function is computable, I think this is true, but I don't know how to prove it.

1

There are 1 best solutions below

6
On BEST ANSWER

False, let $f$ be a constant function. Then $h$ is computable but the $g_i$ can be arbitrarily bad. By a similar trick, we can arrange for $f$ to be also non-computable.