Suppose f and g are functions from N to N, f is computable, and f>=g. Is g also computable?
2026-03-27 10:44:24.1774608264
Are computable functions closed under "less than"?
112 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
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.