Was bedeutet es dass eine Sprache entscheidbar ist?
Eine Sprache L ist entscheidbar genau dann, wenn L und L (das Komplement von L) aufzählbar sind. Beweis. (⇒) Ist L entscheidbar, dann ist L auch aufzählbar. Dreht man zudem die Ergebnisse einer TM, die L entscheidet, um, hat man eine TM, die L entscheidet.
Was kann man mit dem Satz von Rice zeigen?
Benannt wurde der Satz nach Henry Gordon Rice, der ihn 1953 veröffentlichte. Er besagt, dass es unmöglich ist, eine beliebige nicht-triviale Eigenschaft der erzeugten Funktion einer Turing-Maschine (oder eines Algorithmus in einem anderen Berechenbarkeitsmodell) algorithmisch zu entscheiden.
Wann ist etwas entscheidbar?
In der theoretischen Informatik heißt eine Eigenschaft auf einer Menge entscheidbar (auch rekursiv, rekursiv ableitbar), wenn es ein Entscheidungsverfahren für sie gibt. Ein Entscheidungsverfahren ist ein Algorithmus, der für jedes Element der Menge beantworten kann, ob es die Eigenschaft hat oder nicht.
Ist die Klasse der rekursiv Aufzählbaren Sprachen abgeschlossen unter Vereinigung?
Die Menge der rekursiv aufzählbaren Sprachen ist gegenüber Kleenescher Hüllenbildung, Konkatenation, Schnitt und Vereinigung abgeschlossen, nicht jedoch gegenüber dem Komplement.
Wann ist eine Sprache Semi-entscheidbar?
Eine Sprache L ⊆ Σ∗ heißt entscheidbar, falls eine DTM M mit L(M) = L existiert, die jede Eingabe x ∈ Σ∗ entscheidet. Jede von einer DTM M erkannte Sprache heißt semi-entscheidbar.
Was bedeutet semi-entscheidbar?
Eine Menge A ist semi-entscheidbar, wenn sie Definitionsbereich einer berechenbaren Funktion ist. Das bedeutet, daß es einen Algorithmus gibt, der genau auf den Eingaben aus A stoppt. Es gilt der folgende Satz: Eine Menge ist genau dann semi-entscheidbar, wenn sie rekursiv aufzählbar ist.
Wann ist der Satz von Rice nicht anwendbar?
Rice ist dagegen nicht anwendbar auf: • „Hat M mindestens zwei Zustände? “ (keine Eigenschaft von L(M)) • „Ist L(M) semi-entscheibar? “ (trivial) • Der Satz von Rice lässt sich sinngemäß auf alle Turing-mächtigen Formalismen übertragen.
Ist das Halteproblem Semi entscheidbar?
Obwohl das für viele Algorithmen leicht beantwortet werden kann, konnte der Mathematiker Alan Turing beweisen, dass es keinen Algorithmus gibt, der diese Frage für alle möglichen Algorithmen und beliebige Eingaben beantwortet. Das Halteproblem ist somit algorithmisch nicht entscheidbar.
Wann ist eine Sprache kontextsensitiv?
Definition. Eine formale Sprache ist genau dann kontextsensitiv, wenn eine kontextsensitive Grammatik existiert, die diese Sprache erzeugt. Eine kontextsensitive Grammatik ist eine, die in jeder Regel immer ein Nichtterminal in einem Kontext in eine nichtleere Folge von Zeichen (Nichtterminale oder Terminale) ersetzt.
Was bedeutet semi entscheidbar?
Ist eine reguläre Sprache entscheidbar?
Für reguläre Sprachen sind all diese Fragen entscheidbar, d.h., man kann Algorithmen angeben, die diese Fragen immer eindeutig beantworten. Ein Entscheidungsverfahren besteht darin, einen Automaten für die Sprache L zu konstruieren und zu überprüfen, ob er das Wort w akzeptiert oder nicht.