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$

1 Answer 1

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$
9
  • 1
    $\begingroup$ I think that zython would prefer hints to a complete solutions. $\endgroup$
    – xavierm02
    Nov 4, 2017 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, 2017 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, 2017 at 18:35
  • $\begingroup$ while I agree with @xavierm02 the answer is greatly appretiated. thank you for taking the time $\endgroup$
    – zython
    Nov 4, 2017 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, 2017 at 20:15

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.