imported>Känguru1890: Revert - Belegpflicht beachten

2024-09-09T08:55:58Z

Revert - Belegpflicht beachten

Neue Seite

{{Belege fehlen}}
Die '''Diagonalsprache''' ist eine [[Formale Sprache]] aus der [[Theoretische Informatik|theoretischen Informatik]] aus dem Bereich der [[Entscheidbar|Entscheidungsprobleme]]. Sie ist als Menge so konstruiert, dass sie nicht [[Rekursiv aufzählbare Sprache|semi-entscheidbar]] ist, also dass Elemente (Wörter) der Sprache nicht auf [[Algorithmus|algorithmische Weise]] als zu der Sprache gehörig erkannt werden können. Es kann also keine [[Turingmaschine]] geben, die eine Ja-Antwort auf die Frage geben kann, ob ein Element zu der Sprache gehört.

Die Diagonalsprache ist die zentrale Konstruktion im Beweis der [[Entscheidbar|Unentscheidbarkeit]] des [[Halteproblem]]s.

Die Konstruktion der Sprache basiert auf dem Prinzip der [[Cantor-Diagonalisierung|Diagonalisierung]]. Die Diagonalsprache ist die Menge aller Turingmaschinen, die ''nicht'' akzeptieren, wenn sie ihre eigene Kodierung als Eingabe bekommen. Eine Turingmaschine, welche diese Sprache semi-entscheiden könnte, dürfte weder in der Menge noch nicht in der Menge liegen, was zum Widerspruch zu angenommener Semi-Entscheidbarkeit führt.

Das Komplement der Diagonalsprache ist jedoch semi-entscheidbar. Es wird auch als das spezielle Halteproblem bezeichnet und ist das klassische Beispiel dafür, dass es semi-entscheidbare Sprachen gibt, die nicht entscheidbar sind, so dass die Klasse der [[Rekursive Sprache|entscheidbaren Sprachen]] eine echte Teilmenge der Klasse der semi-entscheidbaren Sprachen ist.

== Definition ==

Sei <math>M_w</math> die zu einer Kodierung <math>w</math> gehörige Turingmaschine. Dann ist die Diagonalsprache <math>D</math> definiert als:
<math>D := \{w \mid M_w ~\text{akzeptiert}~ w ~\text{nicht}\}</math>

== D ist nicht semi-entscheidbar ==

Die Diagonalsprache ist nicht semi-entscheidbar, also ist sie auch nicht rekursiv aufzählbar.

Wenn <math>D</math> semi-entscheidbar wäre, gäbe es eine Turingmaschine <math>M</math>, die <math>D</math> semi-entscheidet, so dass alle Elemente <math>x \in D</math> von <math>M</math> akzeptiert werden, und für Elemente <math>x \notin D</math> <math>M</math> hält ohne zu akzeptieren oder nicht hält. Sei <math>w</math> die Kodierung dieser Turingmaschine <math>M</math>, also <math>M=M_w</math>. Wenn <math>M_w</math> mit Eingabe <math>w</math> gestartet wird (also ihre eigene Kodierung entscheiden soll), gibt es folgende Möglichkeiten:

* Angenommen, <math>w \in D</math>:
** <math>M_w</math> müsste <math>w</math> akzeptieren, denn <math>M_w</math> semi-entscheidet <math>D</math>.
** Nach Definition von <math>D</math> ist damit aber <math>w \notin D</math>.
** Widerspruch
* Angenommen, <math>w \notin D</math>:
** <math>M_w</math> darf <math>w</math> nicht akzeptieren, denn <math>M_w</math> semi-entscheidet <math>D</math>.
** Wiederum nach Definition von <math>D</math> ist damit aber <math>w \in D</math>.
** Widerspruch

Somit kann es eine solche Turingmaschine <math>M</math> nicht geben, die <math>D</math> semi-entscheidet.

== Das Komplement von D ist semi-entscheidbar ==

{{Anker|spezielles Halteproblem}}
Das Komplement von <math>D</math>, das sogenannte ''spezielle Halteproblem'', ist jedoch semi-entscheidbar. Definieren wir dieses als <math>K := \{w \mid M_w ~\text{akzeptiert}~ w\}</math>, so akzeptiert folgende Turingmaschine <math>M</math> die Menge <math>K</math>:

* Bei Eingabe <math>w</math> wird <math>M_w</math> bei Eingabe <math>w</math> simuliert.
* Sobald <math>M_w</math> in einer akzeptierenden Konfiguration hält, hält auch <math>M</math> und akzeptiert.

Damit ist klar, dass jede Eingabe <math>w \in K</math> genau dann von <math>M</math> akzeptiert wird, wenn <math>M_w</math> die Eingabe <math>w</math> akzeptiert. Für positive Eingaben, also <math>w \in K</math>, akzeptiert <math>M</math> die Eingabe. Für negative Eingaben, also <math>w \notin K</math>, hält <math>M</math> nicht in akzeptierender Konfiguration, hält also ohne in einen Endzustand zu gelangen oder hält gar nicht. Damit semi-entscheidet <math>M</math> die Sprache <math>K</math>.

Jedoch entscheidet <math>M</math> die Sprache <math>K</math> ''nicht'', denn es kann negative Eingaben geben, auf denen die Turingmaschine nicht hält. Eine <math>K</math> entscheidende Turingmaschine kann es auch gar nicht geben, denn diese würde auch das Komplement von <math>K</math> (nämlich gerade die Diagonalsprache <math>D</math>) entscheiden, was nach obigen Ausführungen nicht sein kann.

[[Kategorie:Theorie formaler Sprachen]]

Diagonalsprache - Versionsgeschichte

imported>Känguru1890: Revert - Belegpflicht beachten