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


2 Answers 2


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.


Computability theory is the study of computable functions :-).

Such functions are usually (in this community) defined as functions that can be expressed with a Turing machine.

More formally a function $f: \mathbb{N} \mapsto \mathbb{N}$ is computable if there exist a Turing $T$ such that if the input to $T$ is $x = 1^n$ the output of $T$ is $1^{f(x)}.$

As it turns out if you define computable functions in this way (programs) they are equivalent to the set of functions one can obtain by using the rules described here. They are called recursive functions since one of the rules for obtaining such functions is a recursive definition (See the 5th rule on wikipedia).

So the reason why recursion theory has much importance is equivalent to the question of why are computable functions important. And the answer to the latter should be quite obvious :)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.