0
$\begingroup$

Suppose we have a partial computable injective function $f: \mathbb N\to \mathbb N$ whose image is computable. I'm trying to show that then the image of every computable set is computable, and that this is false for non-injective functions (by a counterexample).

Suppose $X$ is computable and one wants to check if $y$ lies in $f(X)$. The problem asks to construct an algorithm of how to do this. What I can think of is this: the algorithm accepts $y$. Since $im(f)$ is computable, we one can tell whether $y\in im(f)$. If this is false, then $y\notin f(X)$ either. Suppose $y\in im(f)$. Then for some $x\in dom(f)$, $f(x)=y$. Now it would be natural to find such an $x$ (which would be unique due to injectivity). (And then one would be able to tell whether $x\in X$ or not.) But how to find an algorithm/program doing this? The domain of $f$ may be infinite, so it may be not possible (in finite time) to check for every $x\in dom(f)$ if $f(x)=y$. Also I don't see how the computability of $f$ can be used here.

As for the counterexample, once I understand how to find $x$ with $f(x)=y$, the most trivial counterexample should work, like $\{1,2\}\to \mathbb N, 1,2\mapsto 1$. Is that right?

$\endgroup$
  • $\begingroup$ Do you want the image or the preimage of a computable set $X$? The question says preimage, but judging by your work it looks like you want the image. $\endgroup$ – HallaSurvivor Nov 12 '19 at 3:01
  • $\begingroup$ @HallaSurvivor There was a typo in the title. $\endgroup$ – user700016 Nov 17 '19 at 17:32
1
$\begingroup$

For the first problem, you have the right idea. In fact in your question you have already given an informal description of an algorithm to compute $f(X)$.

Here's the part you seem confused by: you have some $y$ which you know to be in the range of $f$ and you want to find $x$ such that $f(x) = y$. Yes, there are infinitely many possible $x$'s, but the point is that if you start searching for one, eventually you will be successful because you know that such an $x$ exists. The one tricky part is that since $f$ is a partial function, you may run into some candidate $x$'s where $f(x)$ does not converge. The answer is just to try them out in parallel.

Here's what I mean: first check if $f(0)$ converges in one step of computation. Then check if either $f(0)$ or $f(1)$ converge in two steps of computation. Then check if any of $f(0)$, $f(1)$, and $f(2)$ in three steps. Etc. Eventually you will see some $f(x)$ converge and equal $y$ then you can stop the search. Once again, the search is guaranteed to stop after a finite number of steps because $y$ is in the range of $f$.

The ability to perform this kind of unbounded search is what makes computation stronger than e.g. primitive recursion.

For your second problem, nothing with finite range will work because the image of any set will be finite, and therefore computable.

One way to find a counterexample is to recall that every r.e. set is the image of a partial computable function. Start with a partial computable function whose range is a noncomputable r.e. set. Then modify this function in some way so that its range becomes computable but knowing its image on some particular set would tell you the original r.e. set. Or you can just do it by some kind of direct diagonalization.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What do you mean by "in one/two step(s) of computation"? The machinery I know for checking if $f(0)$ converges is Kleene's T predicate. This is done by checking whether there is an $x$ such that $T(f,0,x)$ holds. If $f(0)$ diverges, than the process of finding this $x$ runs forever. So how can we check if $f(0)$ converges in finite time if in the event of divergence of $f(0)$ the program will run forever? $\endgroup$ – user700016 Nov 17 '19 at 17:36
  • $\begingroup$ In terms of the Kleene T predicate, "checking if $f(0)$ converges in one step of computation" means "checking if $T(f, 0, 1)$ holds." The point is that you don't first try to look for $x$ such that $T(f, 0, x)$ holds before doing anything else: you try the first few possible $x$'s and then move on to $f(1)$ then come back to $f(0)$ and try a few more possible $x$'s and so on. $\endgroup$ – Patrick Lutz Nov 18 '19 at 16:40

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.