Are functions with a finite domain and codomain always computable?

Question

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?

Answer 1

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

Answer 2

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.