# 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.