Recursive Language

Recursive Language

In mathematics, logic and computer science, a formal language (a set of finite sequences of symbols taken from a fixed alphabet) is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the language. Equivalently, a formal language is recursive if there exists a total Turing machine (a Turing machine which halts for every given input) which when given a finite sequence of symbols w from the alphabet of the language as input (any string containing only characters in the language's alphabet) accepts only those which are part of the language and rejects all other strings. Recursive languages are also called decidable.

The concept of decidability may be extended to other models of computation. For example one may speak of languages decidable on a non-deterministic Turing machine. Therefore whenever an ambiguity is possible, the synonym for "recursive language" used is Turing-decidable language, rather than simply "decidable".

The class of all recursive languages is often called R, although this name is also used for the class RP.

This type of language was not defined in the Chomsky hierarchy of (Chomsky 1959). All recursive languages are also recursively enumerable. All regular, context-free and context-sensitive languages are recursive.