2
$\begingroup$

This was a question given in a course, without answer. The referenced literature (just a few books) do not cover it, unfortunately.

I think there is no relation with the range as the range of the Halting problem is {0,1} and the range of the successor function is infinite. But I feel like I'm missing some subtleties here.

$\endgroup$
  • $\begingroup$ Well, for one the domain must be infinite; else, the function is computable. $\endgroup$ – dkaeae Jan 23 at 16:56
  • $\begingroup$ If the range is empty or contains a single element, the function is also computable. Nevertheless, two elements already suffice for uncomputability (as you have noted). $\endgroup$ – dkaeae Jan 23 at 16:57
  • $\begingroup$ Thanks! Can you elaborate why these two claims are true? Hard-coding? And for the range, what if it is a partial function? $\endgroup$ – Loren Francis Jan 23 at 17:02
  • 1
    $\begingroup$ Exactly. If the domain is finite, then you can simply hardcode all function values. Ad the second claim: if the range is empty, then the domain must be empty (otherwise it is not a function), and we are back to the finite domain case; if the range has only one element, you can hardcode this as your algorithm's answer. Finally, regarding partial functions: any partial function becomes a function by restricting its domain; thus, it suffices to consider only (non-partial) functions. $\endgroup$ – dkaeae Jan 23 at 17:13
  • 1
    $\begingroup$ @LorenFrancis That's correct. If a partial function has $\{n\}$ as its range, it is computable if and only if its domain is recursively enumerable. $\endgroup$ – chi Jan 25 at 14:03
3
$\begingroup$

(Note: As mentioned by Apass.Jack in the comments, there are apparently two different usages of the terms "domain" and "range". In this answer, I adopt the usages which I am more familiar with. That is, given a function $f\colon X \to Y$ (i.e., $f \subseteq X \times Y$), $X$ is the domain of $f$ in the sense that $f(x)$ is defined for all $x \in X$; similarly, the range (or codomain) $Y$ is a set such that $f(x) \in Y$ for all $x \in X$. Additionally, every function is total; partial functions are explicitly denoted as such.)


Let $f\colon X \to Y$ be a function. The question is: What can we say about the computability of $f$ (strictly) based on $|X|$ and $|Y|$? The following is more or less a structured breakdown of what I have written in the comments:

Domain

  • Case 1: $|X|$ is finite. Then the values $f(x)$ of $x \in X$ may be hardcoded (e.g., as a lookup table) in an algorithm to compute $f$.
  • Case 2: $|X|$ is infinite. There are plenty of both computable and uncomputable functions in this case.

Range

If $Y$ is such that the image $\text{im}(f) = \{ f(x) \mid x \in X \}$ of $f$ is a proper subset of $Y$, then there is not much that can be said about $f$ (e.g., $Y$ could be an infinite set but $f = \{ \}$ the empty function; see Case 1 below). Thus, let us assume $\text{im}(f) = Y$ holds.

  • Case 1: $|Y| = 0$. Then $f$ must be the empty function $\{ \}$, which indicates $|X| = 0$; see "Domain", Case 1.
  • Case 2: $|Y| = 1$. $f$ is computable by an algorithm which ignores its input and outputs the only possible value for $f$.
  • Case 3: $|Y| \ge 2$ but $|Y|$ finite. An example of an uncomputable $f$ is, for instance, the membership relation for the halting problem (as mentioned in the question) or any non-recursive (i.e., undecidable) language; similarly, a computable $f$ would be the membership relation for a recursive (i.e., decidable) language.
  • Case 4: $|Y|$ infinite. As in case 3, there are both computable and uncomputable choices for $f$. For example, $X = Y$ and $f = \text{Id}_X$ is trivially computable. An uncomputable example for $f$ (off the top of my head) would be the busy beaver function.

It is possible to extend these results if further assumptions are made about $X$, $Y$, and $f$. In the general case, however, this is as much (and it is not much, I know) we can say about the computability of $f$.


If we are dealing with a partial function $f \subseteq X \times Y$ instead, note there is always a (maximal) $X' \subseteq X$ such that $f \subseteq X' \times Y$ is a (total) function $X' \to Y$. As pointed out by chi in the comments, it might be tempting to say we may simply generalize the above discussion by considering the total restriction of $f$ instead. This does not work, however, since, for example, the partial function $f \subseteq \mathbb{N}_0 \times \{ 1 \}$ with $f(x) = 1$ if and only if TM number $x$ does not halt is not computable, despite its image having a single element (cnf. "Range", Case 2). Nevertheless, note this is the only case in which the generalization fails.

$\endgroup$
  • 1
    $\begingroup$ In case 2, as the OP mentioned in a comment, we need slightly more. If $f$ is partial with range $\{n\}$, then $f$ may or may not be computable. Precisely, such $f$ is computable iff its domain is r.e. . The very last comment is misleading (IMO) since $X'$ might be a non-r.e. set, so the discussion does not really extend. $\endgroup$ – chi Jan 25 at 14:06
  • $\begingroup$ @chi Duly noted. (Partial functions... ugh...) This is the only case in which the generalization fails though, isn't it? $\endgroup$ – dkaeae Jan 25 at 14:33
  • $\begingroup$ Note that your last $f$ is computable, since the halting problem is r.e. ! To compute $f(x)$ run machine number $x$. When (and if) that halts, return $1$. To craft a non computable $f$ you need, for instance, require $f(x)=1$ when TM $x$ does not halt ($f$ being undefined otherwise). $\endgroup$ – chi Jan 25 at 15:02

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.