About the Words "recursion" and "recursive"

Question

According to Wikipedia, Recursion is the process of repeating items in a self-similar way. On the other hand, the word "recursive" is an adjective and is often used as a synonym of "computable" when speaking about functions $\mathbb N^n\to \mathbb N$. Thus the two words "recursive" and "recursion" have a completely different meaning. That is why I wonder, why these two words are so similar. Is it just an accident? What are the origins of these two words?

Answer 1

The term "recursive" can indeed be synonymous with "computable".

Robert Soare (himself one of the great names of the field) has devoted a number of expository or historical articles to the question of why "computable functions" and "computability" are sometimes called "recursive functions" and "recursion" / "recursive function theory". See, for example, his paper Computability and Recursion (I'm giving a link to the Internet Archive because the original link seems broken right now), published, I think, in Bull. Symbolic Logic in 1996, or Turing and the Art of Classical Computability (same comment), published in 2013 but I don't know where.

The gist of his conclusion, as far as I understand/remember it, is that the original term in the early 1930's was "computable", that it was displaced by "recursive" in 1936, and that he himself (Soare) managed to convince people to go back to using of "computable" through the aforementioned 1996 Bull. Symbolic Logic paper. So Soare strongly advocates the use of "computable".

As for the reason why "recursive" got associated with computability, it lies in the definition of "recursive functions" (now called primitive recursive) by Dedekind and others around 1889, and later of "general recursive functions" (equivalent to computable functions) by Gödel in 1934 and Kleene in 1936. Gödel himself did not use "recursive" to mean "computable" in general: he used "recursive" to refer to that particular definition (viz., general recursive functions), which turns out to be equivalent to Turing machines or the lambda-calculus, to define "computable functions". Calling recursive functions "recursive" is reasonable because it is done by course-of-values recursion (see here for a lengthy discussion), and this is also the reason why recursive functions are called so in programming. Kleene seems to have been (at least if I understand and believe Soare) the main culprit in broadening the scope of the word "recursive" to be synonymous with "computable".

Answer 2

According to Wikipedia, Recursion is the process of repeating items in a self-similar way.

Recursive functions (in the general sense) are functions that are defined in a recursive way, like recurrence relations are sequences that are defined in a recursive way or recursive data structures are data structures that are defined in a recursive way.

In all these cases of recursion we have countable many instances and the definition includes one or more base instances and a way to define new instances from existing instances. The same mathematical object shows up on both sides of the defining equation, albeit for different instances. This is the self-reference in the defintion.

These chains or trees of definition are similar to the chains of implications of inductive reasoning.

Thus the two words "recursive" and "recursion" have a completely different meaning. That is why I wonder, why these two words are so similar. Is it just an accident?

As recursive functions (the ones meant in in the computation theory, see their definition here) are one early accepted concept of how to define computable functions (using constant function, successor function and projection as base instances and composition, primitive recursion and $\mu$-recursion to generate new instances), it became synonymous for computable functions. It could have been some adjective derived from the other concepts (Turing machines, Lambda calculus, certain systems of equations, flow charts / register machines, ..) as well, so much for the historical accident.

For a recursive set in the context of theory of computation or recursive formal language "recursive" is meant in the sense of having computable membership, so "recursive" is roughly meant as "computable".

Thus the term "recursive" went into the theory of computation via recursive functions and then got this additional meaning as "computable" there.

What are the origins of these two words?

Odifreddi's "Classical Recursion Theory" mentions Dedekind's 1888 paper on the nature of numbers as origin of classical recursion theory:

He introduced the study of functions definable of the set $\omega$ of the natural numbers by recurrence using the well-ordered structure of $\omega$, whence the name Recursion Theory.