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.

  • $\begingroup$ So what the professor said is wrong? (2) h has to be computable. mmh $\endgroup$ – Lisa Feb 5 at 16:14
  • $\begingroup$ Sorry, I got the notation wrong. $\endgroup$ – Yuval Filmus Feb 5 at 19:31
  • $\begingroup$ 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? $\endgroup$ – Lisa Feb 5 at 19:47
  • $\begingroup$ 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? $\endgroup$ – Yuval Filmus Feb 5 at 20:13

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.