Is the image of a total, non-decreasing function decidable? This is an exercise I've been struggling with for a while: 


  Let $g : \mathbb{N} \to \mathbb{N}$ be a total, non-decreasing function, i.e. $\forall x &gt; y.\ g(x) \geq g(y)$. Is the image $I_g$ of $g$ a recursive set?


Intuitively, I know that the image $I_{g}$ is not recursive, as $g$ is not strictly monotonic. In fact, it's because that $g$ is not strictly monotonic that $g$ could be a constant function so testing if $y \in I_{g}$  may not finish as it could be that $\forall x, g(x) = c$, $c$ being a constant s.t. $c &lt; y$. Then, testing if there is an $x$ s.t. $g(x) = y$ incrementing $x$ as the $g(x) &lt; y$ may go forever.  On the other hand, it could be that after a while, (for a sufficiently greater $x$) it happens that $g(x) &gt; c$ and $g(x) = y$. If it were stricly monotonic, though, then it would be recursive as I would be able to test if $y = g(x)$ incrementing $x$ until the equality is satisfied or $g(x) &gt; y$ (then $g(x)$ wouldn't get stuck in the same value because $x_1 &gt; x_2$ implies $g(x_1) &gt; g(x_2)$).

However, I haven't been able to prove this formally. Can this intuition become part of a formal proof? Or at least could you give me some help in proving it in some other way? A hint or some outline of a proof would be great.
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.