[Solved]: Is the image of a total, non-decreasing function decidable?

Problem Detail: 

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.

Asked By : PALEN

Answered By : David Richerby

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19732

 Ask a Question

 Download Related Notes/Documents