# Computability of function composition

I have some problems to understand computability and hope you can help me. In the lecture we had following problem:

Consider the three partial functions $$f,g,h\colon N \to N$$, where $$f$$ is computable and $$g$$ is not computable. The following two statements are correct:

1. If $$h(x) = g(f(x))$$, then $$h$$ could be computable.

2. If $$g(x) = h(f(x))$$, then $$h$$ is not computable.

Well, 2 is clear I think, because we know that $$g$$ is not computable and $$f$$ is computable, so $$h$$ has to be not computable, otherwise $$g$$ would be computable.

But 1 is a big problem for me. If $$f$$ is computable and $$g$$ is not computable, how can $$h$$ be computable?

Suppose that $$f(x) = 0$$. Then $$g(f(x))$$ is computable for any function $$g$$, computable or not. This explains 1.
As for 2, the composition of two computable functions is computable, so if both $$f$$ and $$h$$ are computable, so is $$g$$. Since $$f$$ is computable and $$g$$ isn't, the only conclusion is that $$h$$ is not computable.
• No problem :=) But i don't understand 1. if $f(x)=0$ then we get $g(0)$. How can this be computable if $g$ by definition isn't? – Lisa Feb 5 at 19:47
• If $f(x) = 0$ for all $x$, then $g(f(x)) = g(0)$ for all $x$. Now $g(0)$ is just some natural number, say 555. Are you claiming that the function $h(x) = 555$ isn't computable? – Yuval Filmus Feb 5 at 20:13