Why are all finite sets recursive?

2k Views Asked by At

Obviously a finite set for which the members are explicitly given or for which a computable rule is available will be recursive. (By which I mean its characteristic function is computable.)

However, suppose the finite set is such that we don't know where it stops, only that it does stop. Or what about the characteristic function of K restricted to arguments less than n?

3

There are 3 best solutions below

2
On

I don't know what you mean by $K$, but the idea is that, even if you don't know yet where a finite set stops, you know that it does stop. So if you have a finite set $F$ and a number $n$, to check whether $n$ is in $F$ you just start comparing $n$ to members of $F$, and either eventually you run out of members of $F$-in finite time-or you see that $n$ actually is in $F$. That's recursive!

This is not to say that there aren't subtleties, or that people haven't argued that there are problems with the classical notion of recursive set. In practice, for the computationally minded, I'd say it's better to think of a finite set as a set with a given bijection with a natural number. Then it becomes quite straightforward to recurse over it.

0
On

A finite set is recursive because I can simply hardcode all the strings in the language in the TM. Thus it's decidable (aka recursive). Christian's comment above applies.

0
On

Consider the following set: $X=\{0\}$ if the Riemann hypothesis is true, and $X=\{1\}$ otherwise. Then:

  • I can write down a pair of Turing machines $T_0$ and $T_1$, and prove that either $T_0$ computes $X$ or $T_1$ computes $X$.

  • Of course, I can't tell which machine computes $X$ . . .

  • . . . but I don't care: there is one, so $X$ is recursive.

If you understand this example, the case of arbitrary finite sets is no different: we can find a computable sequence of Turing machines $T_{e_i}$ ($i\in\omega$) such that $T_{e_i}$ computes $F_i$, where $\{F_i: i\in\omega\}$ is some enumeration of all finite sets. Then if we know $X$ is finite, we know some $T_{e_i}$ computes $X$. We don't know which . . . but we don't care.


Actually, "we don't care" is putting it a bit strongly. We absolutely do care when we're not looking at just one finite set in a vacuum. For instance, let $K_n=K\cap\{0, . . . , n\}$. Then each $K_n$ is computable, but the $K_n$s are not uniformly computable - there is no computable $f$ such that $T_{f(n)}$ is a Turing machine computing $K_n$. Uniformity issues are indeed a Big Deal. But, if you're just asking whether an individual finite set is computable or not, they don't come up.