# Show that function is not turing-computable?

We have two functions:

$f_1: \mathbb{N}\rightarrow \mathbb{N} \quad$ $f_2: \mathbb{N}\rightarrow \mathbb{N}$

By definition $f_1$ is turing-computable while $f_2$ is not.

Then we define a third funtion $g(n) = f_1(n) + f_2(n)$.

I want to show that $g(n)$ is not turing-computable:

So first assume that $g(n)$ is computable.

That means I can write it like this:

$f_2(n) = g(n)-f_1(n)$

Which (is where I'm not sure) means that $f_2$ can be computed which is a contradiction to the definition, which results that $f_2$ is not turing-computable.

• The idea is correct, but the last equation is wrong: try to substitute $g(n)$ and note a simple error, which is easy to fix. Also, please read the description of the tag "check-my-answer" that you used.
– chi
Nov 4, 2017 at 14:05
• thank you, I fixed it, is there any way one could poke a hole in this logic ? Nov 4, 2017 at 14:10
• Instead of saying "by definition $f_1$ is Turing-computable" you should say "suppose that $f_1$ is not Turing-computable" or "it is given that $f_1$ is not Turing-computable". There is no definition to speak of. Nov 4, 2017 at 14:50