This article is about a class of formal languages as they are studied in mathematics and theoretical computer science. For computer languages that allow a function to call itself recursively, see Recursion (computer science).
This article includes inline citations, but they are not properly formatted. Please improve this article by correcting them. Parenthetical referencing has been deprecated; convert to shortened footnotes.(June 2022) (Learn how and when to remove this message)
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 Turing machine that, when given a finite sequence of symbols as input, always halts and accepts it if it belongs to the language and halts and rejects it otherwise. In Theoretical computer science, such always-halting Turing machines are called total Turing machines or algorithms (Sipser 1997). 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 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 of (Chomsky 1959). All recursive languages are also recursively enumerable. All regular, context-free and context-sensitive languages are recursive.
and 23 Related for: Recursive language information
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...
In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable,...
explained as the consequence of recursion in natural language. This can be understood in terms of a recursive definition of a syntactic category, such as a sentence...
In computability theory, a primitive recursive function is, roughly speaking, a function that can be computed by a computer program whose loops are all...
A recursive acronym is an acronym that refers to itself, and appears most frequently in computer programming. The term was first used in print in 1979...
every context-free language is context-sensitive, every context-sensitive language is recursive and every recursivelanguage is recursively enumerable. These...
computability theory, a set of natural numbers is called computable, recursive, or decidable if there is an algorithm which takes a number as input,...
computer science, a recursive descent parser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent) where...
general recursive fixpoint queries, which compute transitive closures. In standard SQL:1999 hierarchical queries are implemented by way of recursive common...
primitive recursive function of the current step number, and the learner encodes a language guess as a program that enumerates the language i.e. the class...
halt. The halting language is therefore recursively enumerable. It is possible to construct languages which are not even recursively enumerable, however...
target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recursion (or tail-end...
A recursive neural network is a kind of deep neural network created by applying the same set of weights recursively over a structured input, to produce...
In mathematics and computer science, a recursive definition, or inductive definition, is used to define the elements in a set in terms of other elements...
A recursive island or lake, also known as a nested island or lake, is an island or a lake that lies within a lake or an island. For the purposes of defining...
undecidable languages are not recursivelanguages, they may be subsets of Turing recognizable languages: i.e., such undecidable languages may be recursively enumerable...
that compute them. A related notion is the circuit complexity of a recursivelanguage that is decided by a uniform family of circuits C 1 , C 2 , … {\displaystyle...
unlike SNOBOL4 patterns, are not recursive, which gives a distinct computational advantage to SNOBOL4 patterns. (Recursive expressions did appear in Perl...
In computer science, the reentrant mutex (recursive mutex, recursive lock) is a particular type of mutual exclusion (mutex) device that may be locked multiple...
exceedingly complex meanings. It is distinguished by the property of recursivity: for example, a noun phrase can contain another noun phrase (as in "[[the...
computational complexity theory, the complexity class ELEMENTARY of elementary recursive functions is the union of the classes E L E M E N T A R Y = ⋃ k ∈ N k...
Global Information