In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, logic

Logic

In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...

 and computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, a formal language

Formal language

A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...

 (a set of finite sequences of symbol

Symbol (formal)

For other uses see Symbol In logic, symbols build literal utility to illustrate ideas. A symbol is an abstraction, tokens of which may be marks or a configuration of marks which form a particular pattern...

s taken from a fixed alphabet) is called recursive if it is a recursive subset

Recursive set

In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which terminates after a finite amount of time and correctly decides whether or not a given number belongs to the set....

 of the set of all possible finite sequences over the alphabet of the language. Equivalently, a formal language is recursive if there exists a Turing machine

Turing machine

A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...

 which always halts when given a finite sequence of symbols from the alphabet of the language as input and which accepts exactly those words from the alphabet of the language that are part of the language and rejects all other words. Recursive languages are also called decidable or Turing-decidable.

The class of all recursive languages is often called R

R (complexity)

In computational complexity theory, R is the class of decision problems solvable by a Turing machine, which is the set of all recursive languages. R is equal to the set of all total computable functions....

, although this name is also used for the class RP

RP (complexity)

In complexity theory, RP is the complexity class of problems for which a probabilistic Turing machine exists with these properties:* It always runs in polynomial time in the input size...

.

This type of language was not defined in the Chomsky hierarchy

Chomsky hierarchy

Within the field of computer science, specifically in the area of formal languages, the Chomsky hierarchy is a containment hierarchy of classes of formal grammars....

 of . All recursive languages are also recursively enumerable

Recursively enumerable language

In mathematics, logic and computer science, a recursively enumerable language is a type of formal language which is also called partially decidable or Turing-acceptable. It is known as a type-0 language in the Chomsky hierarchy of formal languages...

. All regular

Regular language

In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression....

, context-free

Context-free language

In formal language theory, a context-free language is a language generated by some context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.-Examples:...

 and context-sensitive

Context-sensitive language

In theoretical computer science, a context-sensitive language is a formal language that can be defined by a context-sensitive grammar. That is one of the four types of grammars in the Chomsky hierarchy...

 languages are recursive.

Definitions

There are two equivalent major definitions for the concept of a recursive language:

1. A recursive formal language is a recursive
   Recursive set
   In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which terminates after a finite amount of time and correctly decides whether or not a given number belongs to the set....
   
    subset
   Subset
   In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
   
    in the set of all possible words over the alphabet
   Alphabet
   An alphabet is a standard set of letters—basic written symbols or graphemes—each of which represents a phoneme in a spoken language, either as it exists now or as it was in the past. There are other systems, such as logographies, in which each character represents a word, morpheme, or semantic...
   
    of the language
   Formal language
   A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
   
   .
2. A recursive language is a formal language for which there exists a Turing machine
   Turing machine
   A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
   
    which will, when presented with any finite input string, halt and accept if the string is in the language, and halt and reject otherwise. The Turing machine always halts; it is known as a decider
   Machine that always halts
   In computability theory, a machine that always halts—also called a decider or a total Turing machine —is a Turing machine that halts for every input....
   
    and is said to decide the recursive language.

By the second definition, any decision problem

Decision problem

In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...

 can be shown to be decidable by exhibiting an algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

 for it that terminates on all inputs. An undecidable problem

Undecidable problem

In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer....

 is a problem that is not decidable.

Closure properties

Recursive languages are closed

Closure (mathematics)

In mathematics, a set is said to be closed under some operation if performance of that operation on members of the set always produces a unique member of the same set. For example, the real numbers are closed under subtraction, but the natural numbers are not: 3 and 8 are both natural numbers, but...

 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
  Kleene star
  In mathematical logic and computer science, the Kleene star is a unary operation, either on sets of strings or on sets of symbols or characters. The application of the Kleene star to a set V is written as V*...
  
   
• The image φ(L) under an e-free homomorphism φ
• The concatenation
• The union
• The intersection
• The complement of L
• 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
  Recursively enumerable language
  In mathematics, logic and computer science, a recursively enumerable language is a type of formal language which is also called partially decidable or Turing-acceptable. It is known as a type-0 language in the Chomsky hierarchy of formal languages...
  
  
• Recursion
  Recursion
  Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...