Decidable but nonrecursive sets - MathOverflow

Decidable but nonrecursive sets

2010-08-04T23:00:43Z

Until recently, I believed that recursive=decidable, subscribing to this Wikipedia quote: "In computability theory, a set is decidable, computable, or recursive if there is an algorithm that terminates after a finite amount of time and correctly decides whether or not a given object belongs to the set." But my confidence in equating 'recursive' and 'decidable' has been undermined by encountering intriguing work of Benjamin Wells that seems to point to decidable but nonrecursive theories and sets:

[1] B. Wells, "Is There a Nonrecursive Decidable Equational Theory?" J. Minds Machines, Volume 12, Number 2, 2002, 301-324.

[2] B. Wells, "Hypercomputation by definition," Theor. Comput. Sci., 317, 1-3 (Jun. 2004), 191-207.

He has constructed "finitely based pseudorecursive" equational theories which Tarski (his advisor) believed are decidable. My (shakey) understanding based on these two papers is as follows. $T$ is the equational theory, and $T_n$ is the subset of $T$ consisting of the equations in which no more than $n$ distinct variables occur. Each $T_n$ is recursive, but $T$ is not recursive. For each $T_n$, there is a procedure for deciding whether an arbitrary equation is in $T_n$; so there is a "catalog" of these procedures indexed by $n$. The $T_n$ are individually recursive but they are not "uniformly recursive" in $n$, apparently because the catalog is too chaotically arranged for indexing. Despite reading Wells' description[1] of the sense in which $T$ might or should be considered decidable, I do not understand it. (I am well beyond my expertise here, pushed into this unfamiliar territory by work with a student.)

I have two concrete questions. First, is there later work on nonrecursive but decidable theories? Has Wells' challenge to resolve "the current impasse" been addressed by others? Is there acceptance that there is indeed an impasse?

Second and relatedly, I am especially interested if other models of computation ("hypercomputation"?) have been suggested to capture the sense in which $T$ is decidable by extensions of Turing machines. Wells' 2004 summary[2] is negative: "So far, there has emerged no concrete extension of computing models corresponding to the extension of decidability to finitely based pseudorecursive theories."

Answer by Richard Borcherds for Decidable but nonrecursive sets

2010-08-05T01:53:05Z

The literature on hypercomputation is riddled with claims that some author has found a decidable but nonrecursive set. All such claims that I have seen can charitably be described as somewhat overoptimistic. What often happens is that hidden somewhere in details of the claim is a physically impossible device: typical examples are machines that can run for infinite time, or can do infinitely many steps in finite time, or can work with arbitrary exact real numbers, and so on. A common trick is to quietly change the definition of "computable" to include physically impossible operations. My feeling is that the numerous claims that decidable /= recursive should be treated with extreme skepticism.

Increasing sequences of decidable theories whose union is not decidable, as in Well's paper, do not strike me as that interesting. An trivial way to construct such a sequence is to let T_n be the statements of length at most n about about (say) solvability of Diophantine equations. Since T_n is a finite set of statements it is trivially decidable by some Turing machine, but their union is not.

Answer by Carl Mummert for Decidable but nonrecursive sets

2010-08-05T02:01:38Z

In the field of computability theory, the terms "decidable set", "computable set", and "recursive set" are all formally defined and they all mean the same thing. So, to put it gently, Wells is misusing terminology.

There is an enormous amount of evidence that the formally-defined class of computable functions on the natural numbers is exactly the same as the informally-defined class of effectively calculable functions: the ones for which there is an effective procedure that could, in principle, be carried out by a human with unlimited time, resources, and patience. That is, there is an enormous amount of evidence that the Church-Turing thesis is true in the form "a function is effectively calculable (in the informal sense) if and only if it is computable (in the formal sense)."

Regarding Wells' invocation of Tarski, we'll never really know what Tarski had in mind, because Tarski died within a year of the conversation Wells describes. But Wells' argument that an entire field should redefine the formal term "decidable" based on an off-the-cuff discussion with Tarski is not compelling.

There is a research area known as "hypercomputation" that studies various models of computation that go beyond things computable by Turing machines. The reason that this work is not viewed as evidence against the Church-Turing thesis (as stated above) is that these models don't possess the essential property of being able to be carried out by a patient human using unlimited paper, pencil, and time.

That kind of effectiveness is the heart of Turing computability, and the reason that we use the word "computable" to refer to the Turing computable functions rather than some broader or narrower class of functions.

Answer by Stefan Geschke for Decidable but nonrecursive sets

2010-08-05T08:16:29Z

In some situations there is a distinction between decidability and computability, but it works in the other direction, with decidability being stronger than computability. The example is this: A (possibly partial) function $f$ from $\mathbb N$ to $\mathbb N$ is decidable if its graph is decidable. It is computable (or recursive) if there is an algorithm that for each $n\in\mathbb N$ computes $f(n)$ as long as $n$ is in the domain of $f$ and does not terminate on input $n$, otherwise.

Now, if $f$ is computable (or even decidable), then its domain is c.e. (recursively enumerable). Assume that $f$ has a domain that is c.e. but not computable. Assume further that $f$ has only finitely many values (for instance only the single value $0$). Such computable functions exist. An example is the function that returns $0$ on every $n$ in the halting problem and is otherwise undefined. In this case $f$ is not decidable.