1
$\begingroup$

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 ?

$\endgroup$
2
$\begingroup$

There are many ways to do this, here is one example.

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.

$\endgroup$
  • 1
    $\begingroup$ I think that zython would prefer hints to a complete solutions. $\endgroup$ – xavierm02 Nov 4 '17 at 18:17
  • $\begingroup$ There isn't too much complexity in this, OP is welcome to find other examples based on these. $\endgroup$ – Ariel Nov 4 '17 at 18:20
  • 1
    $\begingroup$ 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. $\endgroup$ – xavierm02 Nov 4 '17 at 18:35
  • $\begingroup$ while I agree with @xavierm02 the answer is greatly appretiated. thank you for taking the time $\endgroup$ – zython Nov 4 '17 at 18:49
  • $\begingroup$ 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 ? $\endgroup$ – zython Nov 5 '17 at 20:15

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.