In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
,
logic and
computer science, a
formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable) if it is a
recursively enumerable subset in the
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
of all possible words over the
alphabet of the language, i.e., if there exists a
Turing machine which will enumerate all valid strings of the language.
Recursively enumerable languages are known as type-0 languages in the
Chomsky hierarchy of formal languages. All
regular,
context-free,
context-sensitive and
recursive 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 subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), 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 ...
in the
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
of all possible words over the
alphabet of the
language.
# A recursively enumerable language is a formal language for which there exists a
Turing machine (or other
computable function) which will enumerate all valid strings of the language. Note that if the language is
infinite, 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 languages, which require that the Turing machine halts in all cases.
All
regular,
context-free,
context-sensitive and
recursive languages are recursively enumerable.
Post's theorem shows that
RE, together with its
complement co-RE, correspond to the first level of the
arithmetical hierarchy.
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
*
Mortality (computability theory)
*
Entscheidungsproblem
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 of ''L''
* the
concatenation of ''L'' and ''P''
* the
union
* 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, their i ...
.
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
*
Recursion
References
* Sipser, M. (1996), ''Introduction to the Theory of Computation'',
PWS Publishing Co PWS may refer to:
* Pressure wave supercharger, a type of super-charger technology
*Performance work statement, term used to summarize the work that needs to be done for a contract
* Personal weather station, a weather station owned and operated by ...
.
* Kozen, D.C. (1997), ''Automata and Computability'',
Springer.
External links
*
Lecture slides
{{Formal languages and grammars
Formal languages
Theory of computation
Mathematics of computing
Alan Turing