[Solved]: How to prove or disprove that f is computable?

Problem Detail: 

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.

Asked By : Gigili

Answered By : Pål GD

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6263

 Ask a Question

 Download Related Notes/Documents