# Is there a relation between the size of the domain/range of a function and its computability?

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.

• Well, for one the domain must be infinite; else, the function is computable. – dkaeae Jan 23 '19 at 16:56
• 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). – dkaeae Jan 23 '19 at 16:57
• Thanks! Can you elaborate why these two claims are true? Hard-coding? And for the range, what if it is a partial function? – Loren Francis Jan 23 '19 at 17:02
• 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. – dkaeae Jan 23 '19 at 17:13
• @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. – chi Jan 25 '19 at 14:03

(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.

• 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. – chi Jan 25 '19 at 14:06
• @chi Duly noted. (Partial functions... ugh...) This is the only case in which the generalization fails though, isn't it? – dkaeae Jan 25 '19 at 14:33
• 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). – chi Jan 25 '19 at 15:02