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. ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle L}$

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. ${\displaystyle D}$

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 : ${\displaystyle L}$ ${\displaystyle K(L)}$

• ${\displaystyle L}$and are recursive (and thus also recursively enumerable). ${\displaystyle K(L)}$
• ${\displaystyle L}$and are not recursively enumerable. ${\displaystyle K(L)}$
• Exactly one of the languages and can be enumerated recursively (but not recursively), the other cannot be enumerated recursively. ${\displaystyle L}$ ${\displaystyle K(L)}$

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 ${\displaystyle L_{1},L_{2}}$ ${\displaystyle f_{1}}$ ${\displaystyle f_{2}}$ ${\displaystyle f(i,j)=f_{1}(i)\cdot f_{2}(j)}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{1}\cdot L_{2}}$

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 . ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$

Individual evidence

1. ^ 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.