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
