2
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Damn... I'm slow. Thanks Andre (Now I think about it, the identity function is computable, so any composition of horrible invertible functions will be computable). The only thing lacking would be to prove the existence of a non-computable function I think. $\endgroup$ Nov 1, 2015 at 20:42
  • $\begingroup$ Which similar trick is that? $\endgroup$ Nov 1, 2015 at 20:43
  • 1
    $\begingroup$ Existence is not hard, there are uncountably many functions and only countably many computable ones. Finding an interesting non-computable is another matter. But that has been done. $\endgroup$ Nov 1, 2015 at 20:46
  • 1
    $\begingroup$ Trick, let $f$ be horrible if all inputs are even, and identically $0$ if any input is odd. Let $g_i$ be non-computable but always giving odd output. Then $h$ is identically $0$. $\endgroup$ Nov 1, 2015 at 20:54
  • $\begingroup$ Great! Thanks a lot, Andre. $\endgroup$ Nov 1, 2015 at 20:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .