If $f$ is computable, $f \geq g$, and $g$ is increasing, then is $g$ computable?

53 Views Asked by At

Suppose we are considering functions on the natural numbers. I once asked if $f$ being computable and $f \geq g$ implies that $g$ is computable. I got a negative answer. However, what if we add the additional hypothesis that $g$ is increasing? Then, is $g$ computable? Also, what if we strengthen the hypothesis by letting $g$ be strictly increasing?

1

There are 1 best solutions below

0
On BEST ANSWER

No. Let $\alpha$ be a non-computable positive real number $0.a_1a_2...$ where $a_i$ are decimal digits. Let $g(n)$ be the $n-$digit integer $a_1...a_n$.Then $g$ is not computable, increasing, and $g(n)<f(n)=10^{n+1}$ which is computable.