In
mathematics,
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premis ...
and
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
, a
formal language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of s ...
is called recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable) if it is a
recursively enumerable subset in the
set of all possible words over the
alphabet
An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a s ...
of the language, i.e., if 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 algor ...
which will enumerate all valid strings of the language.
Recursively enumerable languages are known as type-0 languages in the
Chomsky hierarchy
In formal language theory, computer science and linguistics, the Chomsky hierarchy (also referred to as the Chomsky–Schützenberger hierarchy) is a containment hierarchy of classes of formal grammars.
This hierarchy of grammars was described ...
of formal languages. All
regular
The term regular can mean normal or in accordance with rules. It may refer to:
People
* Moses Regular (born 1971), America football player
Arts, entertainment, and media Music
* "Regular" (Badfinger song)
* Regular tunings of stringed instrum ...
,
context-free,
context-sensitive
Context-sensitive is an adjective meaning "depending on context" or "depending on circumstances". It may refer to:
* Context-sensitive meaning, where meaning depends on context (language use)
** Context-sensitive grammar, a formal grammar in which ...
and
recursive
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathemati ...
languages are recursively enumerable.
The class of all recursively enumerable languages is called
RE.
Definitions
There are three equivalent definitions of a recursively enumerable language:
# A recursively enumerable language is a
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 ...
subset
In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset o ...
in the
set of all possible words over the
alphabet
An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a s ...
of the
language
Language is a structured system of communication. The structure of a language is its grammar and the free components are its vocabulary. Languages are the primary means by which humans communicate, and may be conveyed through a variety of ...
.
# A recursively enumerable language is a formal language 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 algor ...
(or other
computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can d ...
) which will enumerate all valid strings of the language. Note that if the language is
infinite
Infinite may refer to:
Mathematics
*Infinite set, a set that is not a finite set
*Infinity, an abstract concept describing something without any limit
Music
*Infinite (group)
Infinite ( ko, 인피니트; stylized as INFINITE) is a South Ko ...
, the enumerating algorithm provided can be chosen so that it avoids repetitions, since we can test whether the string produced for number ''n'' is "already" produced for a number which is less than ''n''. If it already is produced, use the output for input ''n+1'' instead (recursively), but again, test whether it is "new".
# A recursively enumerable language is a formal language for which there exists a Turing machine (or other computable function) that will halt and accept when presented with any
string
String or strings may refer to:
*String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects
Arts, entertainment, and media Films
* ''Strings'' (1991 film), a Canadian anim ...
in the language as input but may either halt and reject or loop forever when presented with a string not in the language. Contrast this to
recursive language
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 t ...
s, which require that the Turing machine halts in all cases.
All
regular
The term regular can mean normal or in accordance with rules. It may refer to:
People
* Moses Regular (born 1971), America football player
Arts, entertainment, and media Music
* "Regular" (Badfinger song)
* Regular tunings of stringed instrum ...
,
context-free,
context-sensitive
Context-sensitive is an adjective meaning "depending on context" or "depending on circumstances". It may refer to:
* Context-sensitive meaning, where meaning depends on context (language use)
** Context-sensitive grammar, a formal grammar in which ...
and
recursive
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathemati ...
languages are recursively enumerable.
Post's theorem In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.
Background
The statement of Post's theorem uses several concepts relating to definability and re ...
shows that
RE, together with its
complement
A complement is something that completes something else.
Complement may refer specifically to:
The arts
* Complement (music), an interval that, when added to another, spans an octave
** Aggregate complementation, the separation of pitch-clas ...
co-RE, correspond to the first level of the
arithmetical hierarchy
In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain sets based on the complexity of formulas that define th ...
.
Example
The set of
halting turing machines is recursively enumerable but not recursive. Indeed, one can run the Turing Machine and accept if the machine halts, hence it is recursively enumerable. On the other hand, the problem is undecidable.
Some other recursively enumerable languages that are not recursive include:
*
Post correspondence problem
The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Because it is simpler than the halting problem and the ''Entscheidungsproblem'' it is often used in proofs of undecidability.
Definiti ...
*
Mortality (computability theory)
In computability theory, the mortality problem is a decision problem which can be stated as follows:
:''Given a Turing machine, decide whether it halts when run on any configuration (not necessarily a starting one)''
In the statement above, the c ...
*
Entscheidungsproblem
In mathematics and computer science, the ' (, ) is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928. The problem asks for an algorithm that considers, as input, a statement and answers "Yes" or "No" according to whether the stat ...
Closure properties
Recursively enumerable languages (REL) are
closed
Closed may refer to:
Mathematics
* Closure (mathematics), a set, along with operations, for which applying those operations on members always results in a member of the set
* Closed set, a set which contains all its limit points
* Closed interval, ...
under the following operations. That is, if ''L'' and ''P'' are two recursively enumerable languages, then the following languages are recursively enumerable as well:
* the
Kleene star
In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. In mathematics,
it is more commonly known as the free monoid ...
of ''L''
* the
concatenation
In formal language theory and computer programming, string concatenation is the operation of joining character strings end-to-end. For example, the concatenation of "snow" and "ball" is "snowball". In certain formalisations of concatenat ...
of ''L'' and ''P''
* the
union
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''Un ...
* the
intersection
In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, thei ...
.
Recursively enumerable languages are not closed under
set difference
In set theory, the complement of a set , often denoted by (or ), is the set of elements not in .
When all sets in the universe, i.e. all sets under consideration, are considered to be members of a given set , the absolute complement of is the ...
or complementation. The set difference
−
is recursively enumerable if
is recursive. If
is recursively enumerable, then the complement of
is recursively enumerable if and only if
is also recursive.
See also
*
Computably enumerable set
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 ...
*
Recursion
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematic ...
References
* Sipser, M. (1996), ''Introduction to the Theory of Computation'',
PWS Publishing Co.
* Kozen, D.C. (1997), ''Automata and Computability'',
Springer
Springer or springers may refer to:
Publishers
* Springer Science+Business Media, aka Springer International Publishing, a worldwide publishing group founded in 1842 in Germany formerly known as Springer-Verlag.
** Springer Nature, a multinationa ...
.
External links
*
Lecture slides
{{Formal languages and grammars
Formal languages
Theory of computation
Mathematics of computing
Alan Turing