0
$\begingroup$

Are there examples of functions that can be defined computably, though the existence of their range is not computable?

$\endgroup$
5
$\begingroup$

Your question is a bit unclear, but you're probably looking for this example: $$ A(x,n) = \begin{cases} x & \text{ if program $x$ halts within $n$ steps}, \\ \bot & \text{ otherwise}. \end{cases} $$ This is a computable function whose image is the set of halting problems (together with $\bot$).

$\endgroup$
2
$\begingroup$

I believe you're asking:

Is the range of a computable function necessarily computable?

(The phrase "the existence of" is throwing me off a bit.)

If so, the answer is no. The intuitive explanation of why we should expect it to be negative is that in order to tell whether $a$ is in the range of $f$, we seem to have to do an infinite search (does $f(0)=a$? does $f(1)=a$? does $f(2)=a$? ... and this is even worse if $f$ is not total, in which case asking whether $f(0)=a$ itself requires an infinite search in case $f(0)$ doesn't hatl!) in case $a\not\in ran(f)$. This doesn't prove that the answer is negative, but it definitely suggests it.

A set $X$ which is the range of a partial computable function is called computably enumerable (or c.e. - also "recursively enumerable" and "r.e."). This is equivalent to being the domain of a partial computable function, and - as long as $X$ is nonempty - to being the range of a total computable function. (These are good exercises. Incidentally, the analogues of these facts can fail in generalized computability theory.) It turns out that there are lots of different kinds of c.e. sets.

  • The Halting Problem $K$ - the set of all pairs $(e, n)$ such that the $e$th Turing machine halts on input $n$ (this is slightly wrong - usually $K$ is defined as the set of $e$ such that $\Phi_e$ halts on input $e$ - this doesn't change anything, and the definition I've given is slightly easier to work with) - is the most famous example of a c.e. set. It is maximally complicated amongst the c.e. sets: if $X$ is c.e., then $X$ is Turing reducible (even $1$-reducible - that is, injectively many-one reducible) to $K$.

The proof that $K$ is not computable is a nice diagonal argument: if $\Phi_e$ were to compute $K$, consider the machine $\Phi_c$ which, on input $(d, n)$, runs $\Phi_e(d,n)$ and $(i)$ halts if the output is "No" and $(ii)$ loops endlessly if the output is "Yes" (the existence of such a machine follows from the existence of a universal Turing machine). Now can $\Phi_c(c, c)$ halt?

  • Following this, Post asked whether there were any c.e. sets of "intermediate" complexity. This was answered by Friedberg and Muchnik, who showed in fact that there are c.e. sets of incomparable Turing degree. This was the invention of the priority argument, which would over time be developed to increasingly extreme levels of complexity (Friedberg-Muchnik is an instance of the finite injury type of priority argument; Sacks developed the basic infinite injury priority method, and after extensive development Lachlan went one step further with a technique so complicated that it was known for a while as the monster theorem).

  • Primarily - but not exclusively - via priority arguments, a detailed picture of the c.e. sets has emerged. There are far too many fundamental facts about them to mention here; I'll just point the interested reader to Soare's text on the subject, which also functions as a good introduction to computability theory in general. (This paper of Soare, with the same title, may also be of interest - and is definitely shorter! Note that both book and paper are rather old, and no longer represent the state of the art in the field.)

  • Interestingly, although c.e. sets of Turing degree strictly between the computable and that of $K$ are known to exist, no natural examples are known (those constructed by priority arguments are quite artificial). There is a general body of heuristic evidence that in fact no natural examples exist at all, but this gets technical very quickly.

$\endgroup$

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.