2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Daniel Wagner Jun 22 at 16:34
6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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! $\endgroup$ – olinarr Jun 21 at 19:17
  • $\begingroup$ The values $f(a_1),\ldots,f(a_n)$ are hardcoded. We don't need to compute them. $\endgroup$ – Yuval Filmus Jun 21 at 19:20
  • $\begingroup$ Your confusion is addressed in the answers to this question. $\endgroup$ – Yuval Filmus Jun 21 at 19:20
  • $\begingroup$ Thanks, @Yuval Filmus! $\endgroup$ – olinarr Jun 21 at 19:20

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.