Take the 2-minute tour ×

Computability is often defined in terms of recursive functions, recursively enumerable sets, recursive sets. Is the reason behind this – the following:

  • a function that can be computed is a recursive function – ie. parts of such function can be simplified and substituted, and then again simplified, substituted, and so forth

? Is this the meaning behind various recursive tools? Like: $\lambda$-calculus, Markov-algorithms, formal languages.

share|improve this question
There have been many attempts to formalize the notion of computable function. Among the ones you do not mention are $\mu$-recursion, Turing computability, register machine computability, and several others. All these yield provably the same class of functions. That is strong evidence that the intuitive notion of computability has been well captured by all these notions. There cannot be a proof that computability is co-extensive with these notions, since computability is not a formal concept. See Church's Thesis for a discussion. –  André Nicolas Apr 5 '12 at 20:35
@AndréNicolas thanks for the insight-strengthening comment. I was however asking about the term "recursive function" or maybe "recursive" that is often used. It turns out that unless I go to a well prepared course, I will not find a simple explanation of what it means, because it's too basic concept. After I read the various definitions that I mentioned, I think I have developed a proper insight – and I asked if it is correct? –  Mooncer Apr 5 '12 at 20:41

1 Answer 1

up vote 0 down vote accepted

In computability theory a "recursive function" is simply a function that can be effectively computed - by $\lambda$ calculus, or by a Turing machine, or by a register machine, or other equivalent models of computability. Recursive functions are also called "computable functions".

There is more information on the Wikipedia article.

The term "recursive" itself is historical and is not directly related to the idea of "recursive functions" from introductory programming courses.

share|improve this answer
Is the "recursive" maybe historically related to the repeating substitution process, like in Markov algorithms (and probably also $\lambda$-calculus and others, but I am not sure)? It works very similar to "recursive functions" from programming courses you mention. –  Mooncer Apr 5 '12 at 23:24
It came from the concept of "general recursive functions", studied by Church, Herbrand, and Goedel in the 1930s. These were defined via systems of equations whose solutions were sets of mutually recursive functions (in the programming sense of recursive). Because they considered every possible system of recursion equations, they called it "general" recursive, which was later shortened to just "recursive". –  Carl Mummert Apr 6 '12 at 0:26

Your Answer


