# Are functions with a finite domain and codomain always computable?

I apologise if my following reasoning is flawed, but I cannot find the "bug" in it.

Consider two finite subsets of $$\mathbb{N}$$, namely $$A$$ and $$B$$. The set of all functions $$f:A\rightarrow B$$ is clearly finite.

Are the functions in this set computable? I can imagine constructing a huge list of all possible functions $$f:A\rightarrow B$$. For all of these functions $$f$$ in this list, you can construct a table describing the inputs and outputs of $$f$$ (that is, all possible ways to pair the elements of $$A$$ to the elements of $$B$$). From this "view", all such functions $$f$$ seem to be computable, as you have an algorithm (the table) that explains how to compute each $$f$$.

However, consider a turing machine $$M$$ with encoding $$m$$ (with $$m\in\mathbb{N}$$). Per the Halting Theorem, surely an $$M$$ such that $$h(m)$$ is undecidable exists (where $$h(\cdot)$$ decides termination). Thus, consider the function $$f^\star:A\rightarrow B$$ such that, for every $$a\in A$$, $$f(a)=h(m)$$. This function is undecidable, right?

In my mind, it is as if all $$f:A\rightarrow B$$ are computable, but when what happens is that you cannot decide "which" of these $$f^\star$$ is, hence you cannot "in fact" compute it.

Question: Are all functions with finite domain and codomain computable? If yes, why does my second argument fail?

• Perhaps one way of thinking that may be enlightening: $f^*$ is computable, but the function that takes your description of what you want $f^*$ to compute and produces a Turing machine that computes $f^*$ may be uncomputable -- in part, because the set of descriptions is infinite. – Daniel Wagner Jun 22 at 16:34

Your table construction does prove that any function from $$A$$ to $$B$$ is computable. You can easily translate the table into many models of computation. For example, as a rewriting system, each input is an element of $$A$$ and there is one rule $$a \to f(a)$$ for each $$a \in A$$. Or, as a Turing machine, use the tape alphabet $$A \uplus B \uplus \{0\}$$ ($$\uplus$$ is a disjoint union¹), a starting set with a single symbol in $$A$$ followed by all blanks, a set state $$\{q_0, q_1\}$$ where $$q_0$$ is the initial state and $$\{q_1\}$$ is the set of final states, and a finite automaton with a transition $$(q_0, a) \to (q_1, f(a), R)$$ for each element $$a \in A$$. Or, as a program in pseudocode, the concatenation of if x = a: return b for each pair (a, b) such that $$f(a) = b$$. All of these constructions are possible because $$A$$ is finite.

Your second argument does not prove anything.

Thus, consider the function $$f^*: A \to B$$ such that, for every $$a \in A$$, $$f^*(a)=h(m)$$. This function is undecidable, right?

No, there is no reason why this function would not be computable. $$h$$ is uncomputable, granted. But $$f^*$$ is not $$h$$. It's some function that happens to coincide with $$h$$ on a finite subdomain. The restriction of an uncomputable function to a subdomain can be computable. For example, suppose $$g_0$$ is a non-recursive function over the integers ($$g_0 : \mathbb{N} \to \mathbb{N}$$) and define the function $$g : \mathbb{N} \to \mathbb{N}$$ by $$g(2x) = g_0(x)$$ and $$g(2x+1) = 0$$ for every $$x \in \mathbb{N}$$. Well, $$g$$ restricted to the even numbers is non-recursive, since it's just $$g$$ with a trivial reencoding of the argument. But $$g$$ restricted to the odd numbers is recursive, since it's just a contant function.

In fact, by your first argument, the restriction of a function to a finite domain is always computable, regardless of the computability of the original function.

¹ A disjoint union is the union of the sets where each side is “annotated” to remember which side of the union it comes from.

Suppose that $$A = \{ a_1,\ldots,a_n \}$$. Here is a function that computes $$f$$ on input $$x$$:

• If $$x = a_1$$, output $$f(a_1)$$.
• If $$x = a_2$$, output $$f(a_2)$$.
• ...
• If $$x = a_n$$, output $$f(a_n)$$.

The values $$f(a_1),\ldots,f(a_n)$$ are hardcoded.

• I understand, that was my intuition as well. But then, does it mean that we can compute the $f^\star$ I describe in the question? Does that mean that we can solve the halting problem? (Of course not: why not?) Thanks for the quick reply! – olinarr Jun 21 at 19:17
• The values $f(a_1),\ldots,f(a_n)$ are hardcoded. We don't need to compute them. – Yuval Filmus Jun 21 at 19:20
• Your confusion is addressed in the answers to this question. – Yuval Filmus Jun 21 at 19:20
• Thanks, @Yuval Filmus! – olinarr Jun 21 at 19:20