I ask the question because of the following statement found in Mark Burgin's paper, "Algorithmic complexity of recursive and inductive algorithms", Theoretical Computer Science 317 (2004) 31-60 (pg. 34):
It is usually assumed that any finite set is recursively computable and even decidable. When a finite set is given by a list, then this is true. However, this assumption is not valid in a general case when a finite set can be defined by a description [the 'presentation'–my comment]. For instance, let us take the set $X$ of all indices of those Turing machines that have the length of their description less than 1000 and that do not terminate on some input with the length less than 1000. This set is finite, but it is not recursively computable (enumerable).
The problem I see with Prof. Burgin's statement is that computability theory can be (and is usually) formulated in $ZFC$ (the background set theory) in which all sets (regardless of description) can be well-ordered (it should be noted that well-ordered sets, finite or otherwise, can be identified as lists–see Oliver Deiser's paper, "An Axiomatic Theory of Well-Orderings", The Review of Symbolic Logic Volume 4, Issue 2, June 2011, pp. 186-204). As regards finite sets, the Diaconescu-Goodman-Myhill theorem (taken from nlab)
The following are equivalent:
The principle of excluded middle
Finitely indexed sets are projective (in fact, it suffices 2-indexed sets to be projective)
Finite sets are choice (in fact, it suffices for $2$ to be choice)
(Here, a set $A$ is finite or finitely-indexed (respectively) if, for some natural number n, there is a bijection or surjection (respectively) {0,…,n $-$ 1} $\rightarrow $$A$. Also, $A$ is projective iff every entire relation from $A$ to $B$ (so that every element of $A$ is related to some element of $B$), for any $B$, contains a function $A$ $\rightarrow$ $B$, while $B$ is choice iff every entire relation from $A$ to $B$, for any $A$, contains a function $A$ $\rightarrow$ $B$.)
suggests that Prof. Burgin's example should lead one to question the principle of excluded middle, much as the following:
The 2$\uparrow$$\uparrow$$\uparrow$6'th digit in the decimal expansion of $\pi$ = 1
might.
Does it (in the sense that Brouwer's argument against excluded middle would cause one to question it)?
Best Answer
Burgin seems to conflate the notion of computability (existence of an algorithm) with a stronger notion such as our knowing an algorithm or existence of a proof that a particular algorithm agrees with the given presentation.
In his example, the finite set $X$ is computable. Indeed, any finite set is computable by a table look-up algorithm. For Burgin's $X$, we don't know the table, so we don't know the algorithm, and we have no effective way to produce the table from the given description of $X$. But that doesn't make $X$ uncomputable; it just says that $X$ doesn't have the stronger properties mentioned above.