Solving Problems with Finite Test Sets

Abstract

Every finite and every co-finite set of non-negative integers is decidable. This is true and it is not, depending on whether the set is given constructively. A similar constraint is applicable in language theory and many other fields. The constraint is usually understood and, hence, omitted. The phenomenon of a set being finite, but possibly undecidable, is, of course, a consequence of allowing non-constructive arguments in proofs. In this note we discuss a few ramifications of this fact. We start out with showing that every number theoretic statement that can be expressed in first-order logic can be reduced to a finite set, to be called a test set. Thus, if one knew the test set, one could determine the truth of the statement. The crucial point is, of course, that we may not able to know what the finite test set is. Using problems in the class II1 of the arithmetic hierarchy as an example, we establish that the bound on the size of the test set is Turing-complete and that it is upper-bounded by the busy-beaver function. This re-enforces the fact that there is a vast difference between finiteness and constructive finiteness. In the context of the present re-opened discussion about the notion of computability – possibly extending its realm through new computational models derived from physics – the constraint of constructivity of the model itself may add another twist.