What is the relationship between "recursive" or "recursively enumerable" sets and the concept of recursion?
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?
$\endgroup$ 34 Answers
$\begingroup$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.
$\endgroup$ $\begingroup$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.
$\endgroup$ 7 $\begingroup$Quoting from a comment by the original poster: "Is 'recursion' a word in computer science that has two independent meanings ("computable" and "function that calls itself")? Or are those meanings somehow related?"
Yes, they're related, but you could reasonably dislike the way in which they're related.
WHich functions are computable?
Among those are
- the zero function;
- projection functions: $p_k(x_1,\ldots,x_k,\ldots,x_n) = x_k$;
- the successor function: $s(x)=x+1$ (if words in an alphabet, rather than numbers, are the arguments to these functions, then there is one successor function for each letter of the alphabet --- e.g. the one corresponding to "c" appends that letter to the end of the input word);
- compositions of computable functions;
- functions defined by recursion (calling themselves): $f(x_1,\ldots,x_k+1,\ldots,x_n) = \text{some expression involving }f(x_1,\ldots,x_k,\ldots,x_n)$;
- functions defined from other functions by minimalization: $f(x_1,\ldots,x_n) = \min\{y : g(y,x_1,\ldots,x_n)=0\}$.
. . . and no others, if the Church--Turing thesis is right. Thus functions defined by recursion are precisely the functions that are computable.
Minimalization means some computable functions are not everywhere defined, and you don't know whether the algorithm will run forever because the function is undefined. You may be searching for the smallest even number $>2$ that is not the sum of two primes, or the smallest number $>1$ that appears at least nine times in Pascal's triangle (existence of either is an open question). Without including minimalization you get a class of functions that can be shown by a diagonal argument to fail to include all computable functions.
There are other seemingly quite different characterizations of computability. Every general-purpose programming language is such a characterization. But simple characterizations like the one above, which is in effect a simple programming language, are useful, not for writing programs, but for exploring the boundary between what is and what is not computable.
$\endgroup$ $\begingroup$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.
$\endgroup$
