# Recursive language
A **recursive language** is a formal language whose membership question can be settled by an algorithm that halts on every input in a finite number of steps; equivalently, it is a language recognized by a [Turing machine](https://www.edgepedia.org/turing-machine) that halts for all inputs[1](https://xlinux.nist.gov/dads/HTML/decidableLanguage.html). The term is a synonym for *decidable language* and *totally decidable language*, and in much of the older literature the word "recursive" is used where modern texts say "decidable" or "computable"[1](https://xlinux.nist.gov/dads/HTML/decidableLanguage.html) • [2](https://kwarc.info/teaching/sWuV/harrison_handbook-of-practical-logic.pdf).
| Key fact | Detail |
|---|---|
| Definition | Membership can be decided by an algorithm that halts on all inputs in a finite number of steps; equivalently, recognized by a Turing machine that halts for all inputs[1](https://xlinux.nist.gov/dads/HTML/decidableLanguage.html) |
| Alternative names | Decidable language, totally decidable language[1](https://xlinux.nist.gov/dads/HTML/decidableLanguage.html) |
| Characterization | A language is recursive if and only if both it and its complement are recursively enumerable[3](https://arato.inf.unideb.hu/horvath.geza/book/out/html/book.html) |
| Closure | Closed under union, intersection, and complement[4](https://www.enseignement.polytechnique.fr/informatique/INF412/uploads/Main/chap9english-goodINF412ENGLISH.pdf) |
| Place in the hierarchy | Context-sensitive languages ⊊ recursive languages ⊊ recursively enumerable languages ⊊ all languages[3](https://arato.inf.unideb.hu/horvath.geza/book/out/html/book.html) |
| Contrast with RE | Recursively enumerable languages are closed under union and intersection but not under complement[4](https://www.enseignement.polytechnique.fr/informatique/INF412/uploads/Main/chap9english-goodINF412ENGLISH.pdf) • [3](https://arato.inf.unideb.hu/horvath.geza/book/out/html/book.html) |
## Definition and equivalent formulations
The definition is usually given in terms of Turing machines. A Turing machine *M* *recognizes* a language *A* if it accepts exactly the strings of *A*; on a string outside *A* it may either reject or run forever. A language is *Turing-decidable* if there exists a *total* Turing machine, called a decider, that accepts every string in *A* and rejects every string not in *A*[5](https://www.cs.ucdavis.edu/~doty/ecs120slides/06a_TuringMachineComputation-deck.html). The NIST Dictionary of Algorithms and Data Structures gives the algorithm-centered version: membership can be decided by an algorithm that halts on all inputs in a finite number of steps[1](https://xlinux.nist.gov/dads/HTML/decidableLanguage.html).
The two formulations are equivalent, and the class is robust: the same languages are decided by Turing machines with multiple tapes, two-way infinite tapes, random-access memory, and other standard variants of the model[5](https://www.cs.ucdavis.edu/~doty/ecs120slides/06a_TuringMachineComputation-deck.html). By the [Church–Turing thesis](https://www.edgepedia.org/church-turing-thesis), a language decidable by a Turing machine is also decidable by a λ-calculus reduction strategy, by μ-recursive functions, by a [random-access machine](https://www.edgepedia.org/random-access-machine), and by the other formalisms known to compute the same class[6](https://lambdica.org/concepts/decidability/).
A useful characterization connects decidability with [semi-decidability](https://www.edgepedia.org/semi-decidability). A language is *recursively enumerable* (also called Turing-recognizable or semi-decidable) if some Turing machine accepts exactly its members, with no guarantee of halting on non-members[5](https://www.cs.ucdavis.edu/~doty/ecs120slides/06a_TuringMachineComputation-deck.html). A language is recursive if and only if both it and its complement are recursively enumerable: run the two enumerating procedures in alternation, and every word over the alphabet eventually appears on one of the two lists, which tells you whether it belongs to the language[3](https://arato.inf.unideb.hu/horvath.geza/book/out/html/book.html). Equivalently, a language is Turing-decidable if and only if it is both Turing-recognizable and co-Turing-recognizable[5](https://www.cs.ucdavis.edu/~doty/ecs120slides/06a_TuringMachineComputation-deck.html).
## Closure properties
The recursive languages behave well under the basic set operations. If L₁ and L₂ are decidable, then so are L₁ ∪ L₂, L₁ ∩ L₂, and the complement of L₁[4](https://www.enseignement.polytechnique.fr/informatique/INF412/uploads/Main/chap9english-goodINF412ENGLISH.pdf).
The constructions are direct. For the complement, exchange the accepting and rejecting states of the decider; because a decider halts on every input, the modified machine decides the complement[4](https://www.enseignement.polytechnique.fr/informatique/INF412/uploads/Main/chap9english-goodINF412ENGLISH.pdf). For union and intersection, simulate the two deciders in parallel and combine their answers; since both halt on every input, the combined machine does too[4](https://www.enseignement.polytechnique.fr/informatique/INF412/uploads/Main/chap9english-goodINF412ENGLISH.pdf).
The contrast with the recursively enumerable languages is a standard examination point and a genuine structural fact. The semi-decidable languages are closed under union and intersection: a machine accepting the union simulates the two machines in parallel and accepts as soon as either one accepts, and one for the intersection accepts only when both do[4](https://www.enseignement.polytechnique.fr/informatique/INF412/uploads/Main/chap9english-goodINF412ENGLISH.pdf). But the recursively enumerable languages are not closed under complement. Swapping accept and reject states does not work for a recognizer, because a machine that loops on a non-member still loops after the swap, so the modified machine accepts neither the string nor its complement[5](https://www.cs.ucdavis.edu/~doty/ecs120slides/06a_TuringMachineComputation-deck.html). A concrete counterexample comes from a diagonal construction: there is a recursively enumerable language whose complement is not recursively enumerable, which shows the failure of closure directly[3](https://arato.inf.unideb.hu/horvath.geza/book/out/html/book.html).
## Position among language classes
Every recursive language is recursively enumerable, since a decider can simply list the words of the language by enumerating all words and filtering with the decision procedure[3](https://arato.inf.unideb.hu/horvath.geza/book/out/html/book.html). The containments are strict. Every context-sensitive language is recursive, because the word problem can be solved for each context-sensitive language, but a diagonal argument over an enumeration of context-sensitive grammars produces a recursive language that is not context-sensitive[3](https://arato.inf.unideb.hu/horvath.geza/book/out/html/book.html). The resulting chain is
\[ \mathrm{CS} \subsetneq \mathrm{R} \subsetneq \mathrm{RE} \subsetneq \mathrm{AL}, \]
where CS denotes the context-sensitive languages, R the recursive languages, RE the recursively enumerable languages, and AL all languages[3](https://arato.inf.unideb.hu/horvath.geza/book/out/html/book.html). The same diagonal method shows there are languages that are not recursively enumerable at all, so the recursively enumerable class does not contain every language[3](https://arato.inf.unideb.hu/horvath.geza/book/out/html/book.html).
## Origin of the term
In this sense, "recursive" goes back to Stephen Kleene's research on recursive function theory during the 1930s and 1940s; there, a set counts as recursive if its characteristic function can be constructed using primitive recursion, composition, and the μ-operator[6](https://lambdica.org/concepts/decidability/). [Alonzo Church](https://www.edgepedia.org/alonzo-church)'s 1936 paper "An Unsolvable Problem of Elementary Number Theory" defined recursiveness for propositional functions of positive integers, in a definition closely related to one proposed by [Kurt Gödel](https://www.edgepedia.org/kurt-godel) in 1934 lectures at Princeton and credited in part to an unpublished suggestion of [Jacques Herbrand](https://www.edgepedia.org/jacques-herbrand), with principal refinements due to S. C. Kleene[7](https://www.cis.upenn.edu/~cis5110/Church-UnsolvableProblemElementary-1936.pdf). Church and Turing used these notions in 1936 to give negative solutions to Hilbert's Entscheidungsproblem, showing that no algorithm decides validity in first-order logic[8](https://plato.sydney.edu.au/entries/computational-complexity/).
Because "recursive" now also names the general phenomenon of functions and procedures calling themselves, modern textbooks increasingly prefer "decidable" or "computable"; one handbook of practical logic remarks that in much of the literature one sees the overloaded word *recursive* used instead of *decidable* or *computable*[2](https://kwarc.info/teaching/sWuV/harrison_handbook-of-practical-logic.pdf).
## Undecidability and why the class matters
Many natural languages are not recursive. The halting problem, the set of encodings of Turing machines that halt on a given input, is a standard example of a computably enumerable but undecidable set[9](https://homepage.divms.uiowa.edu/~hzhang/countable.pdf). [Rice's theorem](https://www.edgepedia.org/rices-theorem) generalizes this: any non-trivial semantic property of programs, meaning a property that holds of some programs and not others, has an undecidable associated language[10](https://www.cs.uic.edu/~block/courses/cs505-spring2025/lecture-03.html).
These limits shape practice. An analysis that is automatic, terminating, and exact is impossible, so program analysis tools must give up one of the three: testing relaxes termination, static analysis relaxes exactness, and interactive proving relaxes automation[11](https://www.cs.uoregon.edu/research/summerschool/summer23/_lectures/ProgramAnalysis_notes1.pdf). Against this backdrop, the recursive languages mark the boundary of what a guaranteed, always-terminating decision procedure can achieve, and proving that a problem's language is recursive is the basic positive result computability theory asks for.
## References
1. [Decidable language, NIST Dictionary of Algorithms and Data Structures](https://xlinux.nist.gov/dads/HTML/decidableLanguage.html)
2. [Handbook of Practical Logic and Automated Reasoning, chapter 564, "Limitations"](https://kwarc.info/teaching/sWuV/harrison_handbook-of-practical-logic.pdf)
3. [Formal Languages and Automata Theory, chapter 6 (G. Horváth)](https://arato.inf.unideb.hu/horvath.geza/book/out/html/book.html)
4. [Foundations of Computer Science, chapter 9: Undecidability (École Polytechnique INF412)](https://www.enseignement.polytechnique.fr/informatique/INF412/uploads/Main/chap9english-goodINF412ENGLISH.pdf)
5. [ECS 120 Theory of Computation: Turing Machines, Computation and Variants (UC Davis)](https://www.cs.ucdavis.edu/~doty/ecs120slides/06a_TuringMachineComputation-deck.html)
6. [Decidability, Lambdica concepts](https://lambdica.org/concepts/decidability/)
7. [Alonzo Church (1936), An Unsolvable Problem of Elementary Number Theory](https://www.cis.upenn.edu/~cis5110/Church-UnsolvableProblemElementary-1936.pdf)
8. [Computational Complexity Theory, Stanford Encyclopedia of Philosophy](https://plato.sydney.edu.au/entries/computational-complexity/)
9. [Equivalence of Countable and Computable (H. Zhang)](https://homepage.divms.uiowa.edu/~hzhang/countable.pdf)
10. [CS 505 Lecture 3: Undecidability Wrap-up, Rice's Theorem (UIC)](https://www.cs.uic.edu/~block/courses/cs505-spring2025/lecture-03.html)
11. [OPLSS 2023, Program Analysis lecture notes](https://www.cs.uoregon.edu/research/summerschool/summer23/_lectures/ProgramAnalysis_notes1.pdf)
---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Formal languages and automata theory › Decision problems and complexity of formal languages*
*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026; Oct 25, 2026 · Last review: Oct 15, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license