In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
,
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the study of deductively valid inferences or logical truths. It examines how conclusions follow from premises based on the structure o ...
and
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, a recursive (or ''decidable'') language is a
recursive subset of the
Kleene closure
In mathematical logic and theoretical computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation on a set to generate a set of all finite-length strings that are composed of zero or more repetitions of members ...
of an
alphabet
An alphabet is a standard set of letter (alphabet), letters written to represent particular sounds in a spoken language. Specifically, letters largely correspond to phonemes as the smallest sound segments that can distinguish one word from a ...
. Equivalently, a
formal language
In logic, mathematics, computer science, and linguistics, a formal language is a set of strings whose symbols are taken from a set called "alphabet".
The alphabet of a formal language consists of symbols that concatenate into strings (also c ...
is recursive if there exists a Turing machine that
decides the formal language. In
theoretical computer science
Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation.
It is difficult to circumscribe the theoretical areas precisely. The Associati ...
, such always-halting Turing machines are called
total Turing machines or algorithms.
The concept of decidability may be extended to other
models of computation
In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes how ...
. For example, one may speak of languages decidable on a
non-deterministic Turing machine. Therefore, whenever an ambiguity is possible, the synonym used for "recursive language" 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
The Chomsky hierarchy in the fields of formal language theory, computer science, and linguistics, is a containment hierarchy of classes of formal grammars. A formal grammar describes how to form strings from a formal language's alphabet that are v ...
. All recursive languages are also
recursively enumerable
In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:
*There is an algorithm such that the ...
. All
regular,
context-free and
context-sensitive languages are recursive.
Definitions
There are two equivalent major definitions for the concept of a recursive language:
# A recursive language is a
recursive subset of the set of all possible finite-length
words over an
alphabet
An alphabet is a standard set of letter (alphabet), letters written to represent particular sounds in a spoken language. Specifically, letters largely correspond to phonemes as the smallest sound segments that can distinguish one word from a ...
.
# A recursive language is a
formal language
In logic, mathematics, computer science, and linguistics, a formal language is a set of strings whose symbols are taken from a set called "alphabet".
The alphabet of a formal language consists of symbols that concatenate into strings (also c ...
for which there exists a
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
that
decides it.
On the other hand, we can show that a
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...
is decidable by exhibiting a Turing machine running an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
that terminates on all inputs. An
undecidable problem
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an ...
is a problem that is not decidable.
Examples
As noted above, every context-sensitive language is recursive. Thus, a simple example of a recursive language is the set ''L='';
more formally, the set
:
is context-sensitive and therefore recursive.
Examples of decidable languages that are not context-sensitive are more difficult to describe. For one such example, some familiarity with
mathematical logic
Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...
is required:
Presburger arithmetic is the first-order theory of the natural numbers with addition (but without multiplication). While the set of
well-formed formulas in Presburger arithmetic is context-free, every deterministic Turing machine accepting the set of true statements in Presburger arithmetic has a worst-case runtime of at least
, for some constant ''c''>0. Here, ''n'' denotes the length of the given formula. Since every context-sensitive language can be accepted by a
linear bounded automaton, and such an automaton can be simulated by a deterministic Turing machine with worst-case running time at most
for some constant ''c'' , the set of valid formulas in Presburger arithmetic is not context-sensitive. On a positive side, it is known that there is a deterministic Turing machine running in time at most triply exponential in ''n'' that decides the set of true formulas in Presburger arithmetic. Thus, this is an example of a language that is decidable but not context-sensitive.
Closure properties
Recursive languages are
closed under the following operations. That is, if ''L'' and ''P'' are two recursive languages, then the following languages are recursive as well:
* The
Kleene star
In mathematical logic and theoretical computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation on a Set (mathematics), set to generate a set of all finite-length strings that are composed of zero or more repe ...
* The image φ(L) under an
e-free homomorphism φ
* The concatenation
* The union
* The intersection
* The complement of
* The set difference
The last property follows from the fact that the set difference can be expressed in terms of intersection and complement.
See also
*
Recursively enumerable language
*
Computable set
In computability theory, a set of natural numbers is computable (or decidable or recursive) if there is an algorithm that computes the membership of every natural number in a finite number of steps. A set is noncomputable (or undecidable) if it i ...
*
Recursion
Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in m ...
References
*
*
*
*
*
{{Formal languages and grammars
Computability theory
Formal languages
Theory of computation
Recursion