a recursive language

Imagine a perfect librarian who, for any book title you read out, will always come back with a definite YES (we own it) or NO (we do not) — and crucially, will always come back. You never wait forever; the answer is guaranteed to arrive. A recursive language is the set of strings for which such a never-stuck machine exists: a Turing machine that, on every possible input, halts and announces the correct verdict. This is the mathematical core of what we mean by 'there is an algorithm for it'.

Formally, a language L over an alphabet Σ (Sigma) is recursive (the more modern word is DECIDABLE) if some Turing machine M is a DECIDER for L: on every input string w, M halts, and it accepts w exactly when w ∈ L (w is in L) and rejects w exactly when w is not in L. The two outcomes accept and reject are both halting outcomes, so M never runs off into an endless loop. Because the machine always finishes with the right answer, L is the kind of question a computer could reliably solve given enough (but finite) time.

The word 'recursive' here is a historical leftover from the study of recursive functions in the 1930s and has nothing to do with a function calling itself; in plain modern usage just read it as 'decidable'. Many natural problems are recursive: deciding whether a number is prime, whether a string matches a regular expression, whether a DFA accepts a given input. The interesting drama of the theory begins with the languages that are NOT recursive — but to see that gap you first need this clean notion of the problems that always have a halting algorithm.