HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How to prove or disprove that f is computable?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
computableprovethathowdisprove

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#6263, answer score: 4

Revisions (0)

No revisions yet.