How do I show that the range of a non-decreasing, total-recursive function is recursive? I've made reference to this question, but the method used there is not clear to me.
My attempt:
Let $f$ be a non-decreasing, total recursive function. Want to show $im(f)$ is recursive. That is, given any $a \in \mathbb{N}$, we want to show that there exists an algorithm that terminates in finite time and correctly decides whether or not $a \in im(f)$. In other words, we want a computable function $g$ such that $$g(a) = \begin{cases} 1 \text{ if } a \in im(f)\\0\text{ if } a \notin im(f)\end{cases}$$ Then there are two possibilities: $im(f)$ is either finite or infinite. If $im(f)$ is finite, then the construction of $g$ is trivial: let $g = \sum_{i \in im(f)} \phi_a(i)$ where $phi_a$ is the indicator function: $$\phi_a(i) = \begin{cases}1\text{ if } a=i\\0\text{ if } a \neq i\end{cases}$$ We note that $g$ will be either $1$ or $0$ because we assume the set $im(f)$ does not contain repeated elements.
Now suppose $im(f)$ is infinite. Then we can define a computable algorithm as such: for $n \in \mathbb{N} = \{0,1,2,3,\ldots\}$, we compute $f(n)$. If $f(n) = a$, we terminate, returning that $a \in im(f)$, and we are done in finite time (since we required $n$ computations to achieve our result). If $f(n) > a$, we terminate, returning that $a \notin im(f)$, because $f$ is nondecreasing, so for all $x > n$, $f(x) > a$, so $\nexists N \in \mathbb{N}$ such that $f(N) = a$. Again, we will have terminated in finite time.
There is one further possibility: suppose that for all $N > n$, $f(N) = b < a$, i.e. $f$ becomes constant, and the algorithm as described just above will not terminate. However, then $im(f)$ is finite, and thereby computable. So in either case, there exists an algorithm that determines membership of $a \in im(f)$ in finite time (but we do not necessarily know which algorithm this is).