[Solved]: Importance of recursion in computability theory

Problem Detail: 

It is said that computability theory is also called recursion theory. Why is it called like that? Why recursion has this much importance?

Asked By : user5507

Answered By : Andrej Bauer

In the 1920's and 1930's people were trying to figure out what it means to "effectively compute a function" (remember, there were no general purpose computing machines around, and computing was something done by people).

Several definitions of "computable" were proposed, of which three are best known:

1. The $\lambda$-calculus
2. Recursive functions
3. Turing machines

These turned out to define the same class of number-theoretic functions. Because recursive functions are older than Turing machines, and the even older $\lambda$-calculus was not immediately accepted as an adequate notion of computability, the adjective "recursive" was used widely (recursive functions, recursive sets, recursively enumerable sets, etc.)

Later on, there was an effort, popularized by Robert Soare, to change "recursive" to "computable". Thus we nowadays speak of computable functions and computably enumerable sets. But many older textbooks, and many people, still prefer the "recursive" terminology.

So much for the history. We can also ask whether recursion is important for computation from a purely mathematical point of view. The answer is a very definite "yes!". Recursion lies at the basis of general-purpose programming languages (even while loops are just a form of recursion because while p do c is the same as if p then (c; while p do c)), and many fundamental data stuctures, such as lists and trees, are recursive. Recursion is simply unavoidable in computer science, and in computability theory specifically.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7759