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:
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
0 comments:
Post a Comment
Let us know your responses and feedback