# 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 > 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 < y$. Then, testing if there is an $x$ s.t. $g(x) = y$ incrementing $x$ as the $g(x) < 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) > 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) > y$ (then $g(x)$ wouldn't get stuck in the same value because $x_1 > x_2$ implies $g(x_1) > 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.

• So, is $g$ supposed do be computable here? – Andrej Bauer Jan 15 '14 at 19:52
• @AndrejBauer Well, the exercise says nothing about it. Even I thought it was computable. Didn't notice until David pointed it out. – PALEN Jan 15 '14 at 21:01

If $g$ is computable, its range is decidable. If $g$ is bounded, let $m$ be the maximum value in its range. Note that this number is not computable from a description of $g$ but it exists and we are only required to determine whether $g$'s range is computable, not whether the problem "Given $x$ and a description of $g$, determine whether $x$ is in the range of $g$" is decidable. Now, to decide if $x$ is in the range, reject if $m$ exists and $x>m$; otherwise, start computing $g(0), g(1), \dots$. If you find that $g(y)=x$ for some $y$, then accept; otherwise, by monotonicity you will find that $g(y)>x$ for some $y$ and reject.

If $g$ is not computable, its range may or may not be decidable. For example, let $M_0, M_1, \dots$ be an enumeration of all Turing machines and let $$g(x) = |\{i\mid i\leq x \text{ and }M_i(0)\text{ halts}\}|.$$ The range is either all positive integers or all non-negative integers, depending on whether the machine with code zero halts. Whichever of those two sets really is the range of $g$, it is decidable (again, we're not being asked to decide which of these two cases is true; one of them must be). However, if we define $g(0)=0$ and $$g(i+1) = \begin{cases} g(i)+1 & \text{if }M_i(0)\text{ halts}\\ g(i)+2 &\text{otherwise,}\end{cases}$$ then the range of $g$ is undecidable: an algorithm that could find the "gaps" would let you solve the zero-input halting problem.

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.

1. 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 & \text{if T halts in \leq n steps}\\ 0 & \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).$$

2. 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.
• If I got it correctly, what you're saying is that $I_g$ is recursive (there is a $TM$ that computes it) even though we don't know which of the two cases you mentioned is. If $I_g$ is finite we have a $TM$ that computes it. If $I_g$ is infinite, we have a $TM$ that computes it. So there exists a $TM$ that computes it (therefore, it is recursive) even though you can't determine which one is. Am I correct? – PALEN Jan 15 '14 at 15:55
• Does that non-computable step you mentioned affect the set being recursive? – PALEN Jan 15 '14 at 16:34
• Yes, correct. There are two cases, in each of them the set in question is recursive, but there is no computation that would decide between the two cases. – Andrej Bauer Jan 15 '14 at 16:49
• To answer your second question: no, the decidability of $I_g$ is not affected, it is just that we cannot compute the decision procedure from (a code of) $g$. This is a bit like: let $p(x) = x^2$ if Riemann Hypothesis holds, otherwise let $p(x) = x^3$. Is $p$ a polynomial? Yes of course, but unless you solve the Riemann Hypothesis you cannot tell which polynomial it is. – Andrej Bauer Jan 15 '14 at 16:50
• @DavidRicherby: that's a valid point, let's ask the OP what he meant. – Andrej Bauer Jan 15 '14 at 19:52

Note: $\;\;\;$ This answer is wrong for the reason David mentions. $\:$ (I was assuming that $g$ is computable.)

$\operatorname{Range}(\hspace{.02 in}g)\:$ is bounded $\;\;\; \implies \;\;\;$ $\operatorname{Range}(\hspace{.02 in}g)\:$ is finite $\;\;\; \implies$
$\operatorname{Range}(\hspace{.02 in}g)\:$ is a decidable set $\;\;\; \iff \;\;\;$ $I_g$ is a recursive set

$\operatorname{Range}(\hspace{.02 in}g)\:$ is not bounded $\;\;\; \iff \;\;\; (\hspace{.02 in}\forall y\in \mathbb{N})(\exists x\in \mathbb{N})(\hspace{.04 in}y\leq g(x)) \;\;\; \implies$
testing if there is an x s.t. $g(x)=y$ incrementing x as the $g(x)<y$ will eventually halt $\;\;\; \implies$
"output yes or no depending on whether or not that found an x s.t. $g(x)=y$"
is a decision procedure for $\:\operatorname{Range}(\hspace{.02 in}g)$
$\implies \;\;\;$ $\operatorname{Range}(\hspace{.02 in}g)\:$ is a decidable set $\;\;\; \iff \;\;\;$ $I_g$ is a recursive set

Therefore $I_g$ is a recursive set.

• I don't see how you describe a decision procedure. If $g(x) = y-1$ for all but finitely many $z$, then your search never terminates. – Raphael Jan 15 '14 at 8:41
• If $g(x) = y-1$ for all but finitely many $z$, then that decision procedure will increment $x$. $\hspace{1.14 in}$ – user12859 Jan 15 '14 at 10:33
• Ad infinitum, yes. My point exactly. It will never be able to say "No, $y$ is not in $I_g$". – Raphael Jan 15 '14 at 13:29
• It will only repeat ad infinitum if [$\hspace{.02 in}g(x)< y$ for all $x$]. $\:$ However, in that case, $\operatorname{Range}(\hspace{.02 in}g)$ is bounded. $\hspace{.44 in}$ – user12859 Jan 15 '14 at 17:42
• @Raphael Ricky's post as a whole is not a decision procedure: it opens with a non-constructive choice (for a given $g$, either $\mathrm{Range(g)}$ is bounded or $\mathrm{Range(g)}$ is unbounded, but there is no decision procedure to tell which case applies). In either case, a decision procedure exists (in the first case, the image is finite; in the second case, the search is guaranteed to terminate, even if we cannot predict how long it will take). This is the same argument as Andrej's and David's, but I find their presentations easier to read. Ricky, try more English and less microformatting? – Gilles 'SO- stop being evil' Jan 15 '14 at 17:56