2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\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, 2017 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, 2017 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, 2017 at 14:50

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.