# Understanding of recursive functions

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.

-
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

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".
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