Recursively enumerable language

In theoretical computer science a recursively enumerable language or semientscheidbare language is defined by the fact that there is a Turing machine that accepts all words, but no words that are not in. In contrast to recursive languages ​​( decidable languages) must be in the recursively enumerable Turing machine does not stop if a word is not in. That is, under certain circumstances you have to wait for the solution indefinitely. All recursive languages ​​are therefore recursively enumerable.

Recursively enumerable languages ​​form the top step of the Chomsky hierarchy and therefore are also called type -0 languages ​​; the corresponding grammars are the type -0- grammars. They can thus be defined as all the languages ​​whose words can be derived by any formal grammar.

One of the main problems, which is recursively enumerable, but not recursive, the halting problem is so-called.

A non- semi- decidable problem is the so-called diagonal language: the set of encodings of all those Turing machines that do not adhere to their own code as input.

D = { | M does not stop }

Also, the complement of the (semi- decidable ) halting problem is semi- decidable, while the complement of the diagonal language is semi- decidable. In fact, the complement of the support problem of an extension of diagonal language and the complement of the diagonal language is a special case of the holding problem.

An example of a language for which neither they themselves nor its complement is semi- decidable, the equivalence problem for Turing machines (Eq ): the set of pairs of two Turing machines accept the same language.

Eq = { # | L (M1 ) = L (M2 ) }

Easy This property of non- semi- decidability follows from the fact that the halting problem is reducible to this problem and also to its complement. However, it is already established for deterministic pushdown automata instead of general Turing machines.

In general, for a language and its complement always exactly one of the following three properties:

  • And are recursive (and thus recursively enumerable ).
  • And are not recursively enumerable.
  • Exactly one of the languages ​​and recursively enumerable is (but not recursive ), the other is not recursively enumerable.

Seclusion

The amount of recursively enumerable languages ​​is closed under clover Escher shell formation, concatenation, intersection and union, but not to the complement.

Evidence ( sketchy )

Concatenation

If the languages ​​we consider the Aufzählfunktionen and which are each Turing computable. We set and thus have a surjective map from a countable set of all concatenation of a word and a word. Thus we have a Aufzählfunktion for

Section

For the languages ​​requiring an acceptor Turing machine exists. We construct a Turing machine which first, and then simulated. This holds for an input if and only if this input in the section of and is.

Closure (mathematics)
677410
de