A recursive language in mathematics, logic and computer science, is a type of formal language which is also called recursive, decidable or Turing-decidable. The class of all recursive languages is often called R, although this name is also used for the class RP. For other meanings of mathematics or uses of math and maths, see Mathematics (disambiguation) and Math (disambiguation). ... Logic (from Classical Greek λόγος logos; meaning word, thought, idea, argument, account, reason, or principle) is the study of the principles and criteria of valid inference and demonstration. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... In mathematics, logic, and computer science, a formal language is a language that is defined by precise mathematical or machine processable formulas. ... The class of decision problems solvable by a Turing machine. ... In complexity theory, RP (randomized polynomial time) 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 If the correct answer is NO, it always returns NO If the correct answer is YES, then...

This type of language was not defined in the Chomsky hierarchy of (Chomsky 1959). The Chomsky hierarchy is a containment hierarchy of classes of formal grammars that generate formal languages. ...

Definitions

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

1. A recursive formal language is a recursive subset in the set of all possible words over the alphabet of the language.
2. A recursive language is a formal language for which there exists a Turing machine which will, when presented with any 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 and is said to decide the recursive language.

All recursive languages are also recursively enumerable. All regular, context-free and context-sensitive languages are recursive. In computability theory a countable set is called recursive, computable or decidable if we can construct an algorithm which terminates after a finite amount of time and decides whether or not a given element belongs to the set. ... “Superset” redirects here. ... In mathematics, a set can be thought of as any collection of distinct objects considered as a whole. ... ABCs redirects here, for the Alien Big Cats, see British big cats. ... For the test of artificial intelligence, see Turing test. ... In various branches of mathematics and computer science, strings are sequences of various simple objects (symbols, tokens, characters, etc. ... In computability theory, a machine that always halts — also called a decider (Sipser, 1996) — is any abstract machine or model of computation that, contrary to the most general Turing machines, is guaranteed to halt for any particular description and input (see halting problem). ... A recursively enumerable language in mathematics, logic and computer science, is a type of formal language which is also called partially decidable or Turing-recognizable. ... A regular language is a formal language (i. ... The introduction to this article provides insufficient context for those unfamiliar with the subject matter. ... A context-sensitive language is a formal language that can be defined by a context-sensitive grammar. ...

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: In mathematics, the closure C(X) of an object X is defined to be the smallest object that both includes X as a subset and possesses some given property. ...

• the Kleene star L ^*
• the non-erasing homomorphism φ(L)
• the concatenation
• the union
• the intersection
• the complement of L
• the set difference L − P

The last property follows from the fact that the set difference can be expressed in terms of intersection and complement. In mathematical logic and computer science, the Kleene star (or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. ... In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures (such as groups, rings, or vector spaces). ...

References

• Michael Sipser (1997). "Decidability", Introduction to the Theory of Computation. PWS Publishing, 151–170. ISBN 0-534-94728-X. 
• Chomsky, Noam (1959). "On certain formal properties of grammars". Information and Control 2 (2): 137–167. 

Michael Sipser Michael Sipser is a professor of Applied Mathematics in the Theory of Computation Group at the Massachusetts Institute of Technology. ...

See also

• Recursively enumerable language
• Recursion
• Recursive acronym

A recursively enumerable language in mathematics, logic and computer science, is a type of formal language which is also called partially decidable or Turing-recognizable. ... This article is about the concept of recursion. ... A recursive acronym (or occasionally recursive initialism) is an abbreviation which refers to itself in the expression for which it stands. ...

External links