# Decidable language

A

**decidable** or

**recursive language** is a

formal language that is a

recursive set, i.e., for which there exists an

algorithm to solve the following

decision problem: Given

string *w*, does

*w* belong to the language? The algorithm is not allowed to run into an infinite loop and has to produce a YES/NO answer for any input string after a finite amount of time. To formalize the rather vague term "algorithm", one usually employs

Turing machines, but several other equivalent approaches are possible.

All regular, context-free and context-sensitive languages are recursive, but there exist recursively enumerable languagess that are not recursive; one example is given by the halting problem.