View source for Funk transform

{{About|a class of formal languages as they are studied in mathematics and theoretical computer science|computer languages that allow a function to call itself recursively  |Recursion (computer science)}}

In [[mathematics]], [[logic]] and [[computer science]], a [[formal language]] (a [[set (mathematics)|set]] of finite sequences of [[symbol (formal)|symbol]]s taken from a fixed [[alphabet (computer science)|alphabet]]) is called '''recursive''' if it is a [[recursive set|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]] that halts for every given input) that, when given a finite sequence of symbols from the alphabet of the language as input (any string containing only characters in the language's alphabet) accepts only those that 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 (complexity)|R]]''', although this name is also used for the class [[RP (complexity)|RP]].

This type of language was not defined in the [[Chomsky hierarchy]] of {{Harv|Chomsky|1959}}. All recursive languages are also [[recursively enumerable language|recursively enumerable]]. All [[regular language|regular]], [[context-free language|context-free]] and [[context-sensitive language|context-sensitive]] languages are recursive.

== Definitions ==

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

# A recursive formal language is a [[recursive set|recursive]] [[subset]] in the [[set (mathematics)|set]] of all possible words over the [[alphabet]] of the [[formal language|language]].
# A recursive language is a formal language for which there exists a [[Turing machine]] that, when presented with any finite input [[literal string|string]], halts and accept if the string is in the language, and halts and rejects otherwise. The Turing machine always halts: it is known as a [[Machine that always halts|decider]] and is said to ''decide'' the recursive language.

By the second definition, any [[decision problem]] can be shown to be decidable by exhibiting an [[algorithm]] for it that terminates on all inputs. An [[undecidable problem]] is a problem that is not decidable.

== Closure properties ==

Recursive languages are [[closure (mathematics)|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]] <math>L^*</math>
* The image φ(L) under an [[Homomorphism#Homomorphisms and e-free homomorphisms in formal language theory|e-free homomorphism]] φ
* The concatenation <math>L \circ P</math>
* The union <math>L \cup P</math>
* The intersection <math>L \cap P</math>
* The complement of <math>L</math>
* The set difference <math>L - P</math>

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]]
*[[Recursion]]

== References ==
* {{Cite book|author = [[Michael Sipser]] | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | chapter = Decidability | pages = 151–170 | isbn = 0-534-94728-X|ref = harv|postscript = <!--None-->}}
* {{cite journal | last = Chomsky | first = Noam | year = 1959 | title = On certain formal properties of grammars | journal = Information and Control | volume = 2 | issue = 2 | pages = 137–167 | doi = 10.1016/S0019-9958(59)90362-6 | ref = harv}}

{{Formal languages and grammars}}

[[Category:Computability theory]]
[[Category:Formal languages]]
[[Category:Theory of computation]]
[[Category:Recursion]]