1
$\begingroup$

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.

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

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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:

  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.
Improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – PALEN Jan 15 '14 at 15:55
  • $\begingroup$ Does that non-computable step you mentioned affect the set being recursive? $\endgroup$ – PALEN Jan 15 '14 at 16:34
  • 1
    $\begingroup$ 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. $\endgroup$ – Andrej Bauer Jan 15 '14 at 16:49
  • 1
    $\begingroup$ 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. $\endgroup$ – Andrej Bauer Jan 15 '14 at 16:50
  • 1
    $\begingroup$ @DavidRicherby: that's a valid point, let's ask the OP what he meant. $\endgroup$ – Andrej Bauer Jan 15 '14 at 19:52
0
$\begingroup$

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.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael♦ Jan 15 '14 at 8:41
  • $\begingroup$ If $g(x) = y-1$ for all but finitely many $z$, then that decision procedure will increment $x$. $\hspace{1.14 in}$ $\endgroup$ – user12859 Jan 15 '14 at 10:33
  • 2
    $\begingroup$ Ad infinitum, yes. My point exactly. It will never be able to say "No, $y$ is not in $I_g$". $\endgroup$ – Raphael♦ Jan 15 '14 at 13:29
  • $\begingroup$ 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}$ $\endgroup$ – user12859 Jan 15 '14 at 17:42
  • 1
    $\begingroup$ @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? $\endgroup$ – Gilles 'SO- stop being evil' Jan 15 '14 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.