Pergunta

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.

Foi útil?

Solução

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.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top