5

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?

Ray
  • 91
  • 3
    You are misinterpreting the definition of "computable." A set is computable if there is a Turing machine that decides membership in the set. This is just an abstract existence requirement, we are not required to actually deliver a concrete TM. –  Oct 24 '15 at 22:34

3 Answers3

4

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.

Noah Schweber
  • 245,398
1

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.

starflyer
  • 550
0

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.

Kevin Carlson
  • 52,457
  • 4
  • 59
  • 113
  • Thankyou for your responses. But the finite set you described has its members given explicitly. What about a finite r.e. set? Such as the set of indices of self halting TMs where the indices are less than n? – Ray Oct 25 '15 at 14:00
  • Hopefully the answer below clarifies the situation. There may not be a Turing machine that decides which Turing machine decides that set, but there's still a Turing machine that decides it. – Kevin Carlson Oct 25 '15 at 22:35