What is the relationship between "recursive" or "recursively enumerable" sets and the concept of recursion?

Question

I understand that "recursive" sets are those that can be completely decided by an algorithm, while "recursively enumerable" sets can be listed by an algorithm (but not necessarily decided). I am curious why the word "recursive" appears in their name. What does the concept of decidability/recognizability have to do with functions that call themselves?

Answer 1

There's a history here. In thumbnail version, in the 1930s various attempts where made to formally characterize the intuitively computable numerical functions, and relatedly the effectively decidable sets of numbers (i.e. those whose membership can be decided by a computable function). Thus we encounter as various formal accounts of computability Church's idea of $\lambda$-computability, Turing computability, Herbrand-Gödel computability, and Gödel and Kleene's $\mu$-recursiveness (and more!). Of these, it is in the latter formal definition of computability where the notion of recursion in the sense of a function calling itself centrally features.

Now as a matter of technical fact, the $\lambda$-computable function, the Turing-computable functions, the Herbrand-Gödel computable functions, and the ($\mu$)-recursive functions turn out to be the same class of functions. And for various reasons the preferred term for this class of functions became "recursive".

The technical fact that all these attempts (and other later ones) to characterize the intuitively computable functions converge on the recursive functions leads to the Church-Turing thesis that the computable functions in the intuitive sense just are these recursive functions (and the decidable sets of numbers are the recursive sets, i.e. those with a recursive characteristic function).

I wouldn't myself say that "computable" means "recursive" (nor would I recommend a linguistic reform to this effect). Rather I'd put it like this: it is a discovery that the intuitive notion of an algorithmically computable function (dressed up a bit) picks out the class of recursive functions.

Answer 2

Today in the context of the branch of mathematics called recursion theory or computability theory, the term recursive and computable mean the same thing. The term decidable also mean the same thing but more often used in the context of logical theories or in textbook more focused on computer science. All these terms means there is an effective procedure to determine membership in some sets. Effective formally means accepted by a Turing Machine, $\mu$-recursive function, unlimited register machine, $\lambda$ calculus, etc.

The terms computable enumerable, recursively enumerable, recognizable all mean the same thing. They are the domain of the algorithms, the range of a total algorithm, the $\Sigma_1^0$ definable subsets of $\omega$, etc.

As I mentioned above, there are several formal model of computation that define the concept of being computable (decidable, recursive). I suspect the name "recursion" comes from one of the earlier method of computation. I believe Kleene proved many of the basic theorems of computability theory using primitive recursive functions and the $\mu$-recursive functions. Possibly this is where the term recursion comes from.

Soare argues in the 1990s that the name of the field called Recursion Theory should be called Computability Theory. The following papers discusses the history of the name "recursion" and "computability" and why he thinks computability is more appropriate.

http://www.people.cs.uchicago.edu/~soare/History/compute.pdf http://www.people.cs.uchicago.edu/~soare/History/siena.pdf

Answer 3

What does the concept of decidability/recognizability have to do with functions that call themselves?

The primitive recursive functions are closely related to the functions that call themselves. For the general or $\mu$-recursive function, and additional minimization operation is allowed. This minimization operation doesn't always define a function, hence it leads to partial functions.

However, I have to admit that the Ackermann function is not primitive recursive (it is a $\mu$-recursive total function), still its definition looks like a function that is calling itself. So the relation between $\mu$-recursive (total) functions and functions that call themselves is deeper than a simple misnomer.