0
$\begingroup$

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.

  • 0
    @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?2012-04-05

1 Answers 1

0

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.

  • 3
    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".2012-04-06