Pergunta

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.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top