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?
Asked
Active
Viewed 52 times
0
-
Just count the number of increasing functions below your favorite appropriate $f$. – Noah Schweber Feb 11 '22 at 20:07
-
I guess the OP wanted integer valued functions. Otherwise it is too easy, indeed. – markvs Feb 11 '22 at 20:11
1 Answers
6
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.
markvs
- 19,653