Is the image of a total, non-decreasing function decidable?
I am assuming in my answer that $g$ is to be taken as computable, given the comments in the question. For non-computable $g$ see David's answer.

There are two answers:


There is no uniform decision procedure for membership in the image of a non-decreasing function. For suppose we had a decision procedure $P$ which would decide whether $n \in I_g$ on input $\langle\ulcorner g \urcorner, n\rangle$. (Here $\langle\ulcorner g \urcorner$ is a suitable encoding of the Turing machine that computes $g$.) Then we could implement the Halting oracle as follows. Given a Turing machine $T$ let $g$ be
$$g(n) = \begin{cases}
1 &amp; \text{if $T$ halts in $\leq n$ steps}\\
0 &amp; \text{if $T$ does not halt in $\leq n$ steps}\\
\end{cases}
$$
Clearly, $g$ is a monotone map and so we would have
$$\text{$T$ halts} \iff P(\langle\ulcorner g \urcorner, 1\rangle).$$
For each such $g$ its image is decidable, but non-uniformly in $g$. (This means my proof will somewhere make a non-computable step.) Consider any non-decreasing $g$. Then either $I_g$ is finite or $I_g$ is infinite (that was the non-computable step):


if $I_g$ is finite then it is recursive
if $I_g$ is infinite then we can use the usual trick: given and $n$, enumerate the values $g(0), g(1), g(2), \ldots$ and wait until they get larger than $n$, which they will as $I_g$ is infinite. Once they do, see whether $n$ has been enumerated.