Suppose f and g are functions from N to N, f is computable, and f>=g. Is g also computable?
Asked
Active
Viewed 111 times
1 Answers
4
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.
Ben Grossmann
- 225,327
-
2For a specific example, let $g(n)$ be the function which returns $0$ if $n$ encodes a Turing machine that halts (pick any such encoding) and $1$ otherwise. – Qiaochu Yuan May 02 '14 at 03:50
-
@QiaochuYuan neat example! – Ben Grossmann May 02 '14 at 03:57