4
$\begingroup$

If $f(x_1,\dots, x_n)$ is a total function that for some constant $K$, $f(x_1,\dots, x_n) \leq K$ for all $x_1,\dots, x_n$ then $f$ is computable.

I want some hints on how to prove/disprove the above claim. This an exercise from the book Computability, Complexity, and Languages. As I didn't find the solutions to the exercises online, I want to see a formal solution of such problems, if possible.

$\endgroup$
  • 5
    $\begingroup$ Hint: try to find a counterexample using a well-known uncomputable (undecidable) set ... $\endgroup$ – Vor Oct 23 '12 at 12:27
4
$\begingroup$

Define the function $f: \mathbb{N} \to \{0,1\}$ as follows. Let $f(x) = 1$ if turing machine $x$ halts on itself as input and $f(x) = 0$ otherwise. Then for all $x$, we have that $f(x) \leq 1$. Yet, if $f$ is computable, then the Halting problem should be decidable.

$\endgroup$
  • $\begingroup$ If you'll excuse me, does it mean that f is not computable? Just to make sure I get it right. $\endgroup$ – Gigili Oct 26 '12 at 5:45
  • $\begingroup$ Yes, the Halting problem is undecidable (this is something you should know if you ever try solving such exercises), and if $f$ being computable implies $\bot$ than $f$ cannot be computable. $\endgroup$ – Pål GD Oct 27 '12 at 13:14

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.