# Construct a computable function from non-computable funciton

Let $f_1$ and $f_2$ be two functions from $\mathbb{N} \rightarrow \mathbb{N}$.

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

$h(i)$ is a function that returns $1$ when $f_1(i) = f_2(i)$ and $0$ else.

The challenge is to construct $f_1$ and $f_2$ so that $h(i)$ is computable and additionally so that it is not.

My thought process is that for either scenario we have to use the computability and non-computability property and pass that forward to $h(i)$ but I am not sure how.

One thought I had to make $h(i)$ uncomputable is to define $f_2$ and $f_1$ on a for a small set of numbers and let $f_2$ be uncomputable on all other numbers. This way I cannot compute if $f_2 = f_1$ so I cannot compute wether $h(i)$ outputs $1$ or $0$.

But I dont know how to make $h(i)$ computable given the requirements that $f_2$ be uncomputable.

Can anyone nudge me in the right direction ?

To make $h$ uncomputable, you can choose $f_1$ to be the constant $1$ function, and $f_2$ to be any non computable binary function, i.e. whose range is $\{0,1\}$. In that case $h=f_2$ is not computable. In fact, when $f_1,f_2$ are binary functions, $h$ is never computable (why?).
To make $h$ computable you can let $f_1$ be the constant $1$ function, and $f_2$ be any non computable function whose range is $\mathbb{N}\setminus\{1\}$. In that case $h$ is zero everywhere.
• Nevertheless, I think you answer would be improved by saying to try to find solutions where $f_1$ or $h$ is constant, and putting the rest in a spoiler. – xavierm02 Nov 4 '17 at 18:35
• just so I understand correctly; if $f_1, f_2$ are binary functions $h$ is never computable because $h$ would equal $h = f_1 XNOR f_2$ which is also uncomputable ? correct ? – zython Nov 5 '17 at 20:15