5
$\begingroup$

Why did the sets of languages accepted/decided by a TM get the name Recursively Enumerable and Recursive, respectively?

$\endgroup$
  • 3
    $\begingroup$ also see the answers of this question to get some perspective $\endgroup$ – Ran G. Apr 11 '13 at 4:17
4
$\begingroup$

A recursive set is synonymous with computable set. In the beginning of computer science, the notion of computer had not been completely fleshed out, and there were various ideas on the matter. These ran from Turing's machines, Church's Lambda calculus, and Kleene-Gödels recursive function theory. The idea is a set is computable if its elements can be decided by a (terminating) algorithm.

Recursively enumerable sets are more general. It turns out that not every subset of the natural numbers is decidable by an algorithm. However, for some sets, we can give a procedure (possibly non-terminating) that will enumerate the elements of the set (enumerate is used because each number appears exactly once thus a bijection from the natural numbers to the set in question is defined). This is equivalent to saying that the set is semi-decidable in more modern terms.

$\endgroup$
  • $\begingroup$ This is true (mostly -- a recursive enumeration doesn't have to be a bijection) but it doesn't answer the question at all, which is why are the names "recursive" and "recursively enumerable" used, not what do they mean. $\endgroup$ – David Richerby Dec 5 '13 at 9:14
  • $\begingroup$ The notion of a computer was not around; the notion of a recursive function was. The answer linked to by the remark that this is a duplicate question is very good if you are interested. $\endgroup$ – Jonathan Gallagher Dec 13 '13 at 19:07

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