Diagonal language

This article or the following section is not adequately provided with supporting documents ( e.g. individual evidence ). Information without sufficient evidence could be removed soon. Please help Wikipedia by researching the information and including good evidence.

The diagonal language is a formal language from theoretical computer science from the area of decision problems . It is constructed as a set in such a way that it is not semi-decidable , i.e. that elements (words) of the language cannot be recognized algorithmically as belonging to the language. So there can be no Turing machine that can give a yes answer to the question whether an element belongs to the language.

The diagonal language is the central construction in the proof of the undecidability of the holding problem .

The construction of language is based on the principle of diagonalization . The diagonal language is the set of all Turing machines that do not accept when they receive their own coding as input. A Turing machine that could semi-decide this language should be neither in the set nor not in the set, which leads to the contradiction of assumed semi-decidability.

However, the complement of the diagonal language is semi-decidable. It is also known as the special halting problem and is the classic example that there are semi-decidable languages ​​that are not decidable, so the class of decidable languages ​​is a true subset of the class of semi-decidable languages.

definition

Let be the Turing machine belonging to a coding . Then the diagonal language is defined as: ${\displaystyle M_{w}}$ ${\displaystyle w}$ ${\displaystyle D}$ ${\displaystyle D:=\{w\mid M_{w}~{\text{akzeptiert}}~w~{\text{nicht}}\}}$

D is not semi-decidable

The diagonal language is not semi-decidable, so it is not recursively enumerable.

If it were semi-decidable, there would be a Turing machine that semi-decides so that all elements of are accepted and holds for elements without accepting or not. Be the coding of this Turing machine , so . If you start with input (i.e. should decide your own coding), you have the following options: ${\displaystyle D}$ ${\displaystyle M}$ ${\displaystyle D}$ ${\displaystyle x\in D}$ ${\displaystyle M}$ ${\displaystyle x\notin D}$ ${\displaystyle M}$ ${\displaystyle w}$ ${\displaystyle M}$ ${\displaystyle M=M_{w}}$ ${\displaystyle M_{w}}$ ${\displaystyle w}$

• Suppose : ${\displaystyle w\in D}$
  • ${\displaystyle M_{w}}$would have to accept, because semi-decides . ${\displaystyle w}$ ${\displaystyle M_{w}}$ ${\displaystyle D}$
  • However, according to the definition of is . ${\displaystyle D}$ ${\displaystyle w\notin D}$
  • Contradiction
• Suppose : ${\displaystyle w\notin D}$
  • ${\displaystyle M_{w}}$must not accept, because semi-decides . ${\displaystyle w}$ ${\displaystyle M_{w}}$ ${\displaystyle D}$
  • But again according to the definition of is . ${\displaystyle D}$ ${\displaystyle w\in D}$
  • Contradiction

Thus there can not be such a Turing machine that semi-decides. ${\displaystyle M}$ ${\displaystyle D}$

The complement of D is semi-decidable

However, the complement of , the so-called special holding problem , is semi-decidable. If we define this as , the following Turing machine accepts the set : ${\displaystyle D}$ ${\displaystyle K:=\{w\mid M_{w}~{\text{akzeptiert}}~w\}}$ ${\displaystyle M}$ ${\displaystyle K}$

• When entered , it is simulated when entered . ${\displaystyle w}$ ${\displaystyle M_{w}}$ ${\displaystyle w}$
• As soon as it stops in an accepting configuration, it stops and accepts. ${\displaystyle M_{w}}$ ${\displaystyle M}$

So it is clear that every input is accepted by if and only if the input is accepted. For positive entries, that is , accept the entry. For negative inputs, that is , it does not hold in an accepting configuration, i.e. holds without reaching an end state or does not hold at all. So the language semi-decides . ${\displaystyle w\in K}$ ${\displaystyle M}$ ${\displaystyle M_{w}}$ ${\displaystyle w}$ ${\displaystyle w\in K}$ ${\displaystyle M}$ ${\displaystyle w\notin K}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle K}$

However, the language does not decide , because there can be negative inputs on which the Turing machine does not stop. There cannot even be a decisive Turing machine, because this would also decide the complement of (namely precisely the diagonal language ), which, according to the above, cannot be. ${\displaystyle M}$ ${\displaystyle K}$ ${\displaystyle K}$ ${\displaystyle K}$ ${\displaystyle D}$