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.

  • $\begingroup$ 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. $\endgroup$ – chi Nov 4 '17 at 14:05
  • $\begingroup$ thank you, I fixed it, is there any way one could poke a hole in this logic ? $\endgroup$ – zython Nov 4 '17 at 14:10
  • 2
    $\begingroup$ 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. $\endgroup$ – Andrej Bauer Nov 4 '17 at 14:50

This proof is correct as written, well done :) Remember this pattern, because an identical proof can be used in a wide variety of similar problems such as rational/irrational numbers and polynomials/non-polynomials


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.