# How to prove or disprove that f is computable?

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.

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

## 1 Answer

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.

• If you'll excuse me, does it mean that f is not computable? Just to make sure I get it right. – Gigili Oct 26 '12 at 5:45
• 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. – Pål GD Oct 27 '12 at 13:14