Are computable functions closed under "less than"?

112 Views Asked by At

Suppose f and g are functions from N to N, f is computable, and f>=g. Is g also computable?

1

There are 1 best solutions below

2
On BEST ANSWER

Answer: no.

There are uncountably many functions on $N$ that only attain the values $\{0,1\}$, but there are only countably many computable functions. So, there must be a non-computable function $g(n)$ such that $g(n) \in \{0,1\}$ for all $n \in N$.

Take $f(n) = 2$. The function $f$ is computable, $f \geq g$, but $g$ is not computable.