Recursively enumerable language
In theoretical computer science , a recursively enumerable language (also known as a semi-decidable or recognizable language ) is defined by the fact that there is a Turing machine that accepts all words from , but not words that are not in . In contrast to recursive languages (decidable languages), the Turing machine does not have to stop with recursively enumerable languages if a word is not in . That means, you may have to wait indefinitely for the solution . All recursive languages can therefore also be enumerated recursively.
Languages that can be enumerated recursively form the top level of the Chomsky hierarchy and are therefore also called Type 0 languages ; the corresponding grammars are the type 0 grammars. They can thus also be defined as all those languages whose words can be derived from any formal grammar .
One of the most important problems that is recursively enumerable but not recursive is what is known as the stall problem .
A problem that is not semi-decidable is the so-called diagonal language : the set of codings for all those Turing machines that do not use their own coding as input.
D = {< M > | M doesn't stop < M >}
The complement of the (semi-decidable) holding problem is also not semi-decidable, while the complement of the diagonal language is semi-decidable. Indeed, the complement of the halting problem is an extension of the diagonal language and the complement of the diagonal language is a special case of the halting problem.
An example of a language for which neither it nor its complement is semi-decidable is the equivalence problem for Turing machines ( Eq ): the set of pairs of two Turing machines that accept the same language.
Eq = {< M 1> # < M 2> | L ( M 1) = L ( M 2)}
This property of non-semi-decidability follows easily from the fact that the holding problem can be reduced to this problem and also to its complement. However, it already applies to deterministic push-down automata instead of general Turing machines.
In general, exactly one of the following three properties always applies to a language and its complement :
- and are recursive (and thus also recursively enumerable).
- and are not recursively enumerable.
- Exactly one of the languages and can be enumerated recursively (but not recursively), the other cannot be enumerated recursively.
Seclusion
The set of recursively enumerable languages is closed with respect to Kleenian envelope formation , concatenation , cut and union , but not with respect to the complement .
Evidence (sketchy)
Concatenation
Given the languages , we consider the enumeration functions and which can be calculated in each case. We set and thus have a surjective mapping from a countable set to all concatenation of one word and one word . So we have a list function for
cut
There is an acceptor Turing machine for each of the languages and . We construct a Turing machine, which simulates first , and then . This holds for an input exactly when this input lies in the intersection of and .
Individual evidence
- ^ Uwe Schöning: Theoretical Computer Science - in short . 5th edition. Spectrum, Heidelberg et al. 2008, ISBN 978-3-8274-1824-1 , ( Spectrum university paperback ), p. 81.