Semi-entscheidbare Menge
aus Wikipedia, der freien Enzyklopädie
Als semi-entscheidbare Menge (auch halb-entscheidbare Menge) wird in der Berechenbarkeitstheorie eine Menge A bezüglich einer Grundmenge M bezeichnet, wenn ihre partielle charakteristische Funktion 
definiert durch
berechenbar ist. Die Menge M muss dazu gödelisierbar sein. In der Theorie setzt man zum einfacheren Vergleich direkt 
oder M = {0,1} * voraus. Im letzteren Fall hat man die Menge als das Wortproblem einer formalen Sprache dargestellt.
Hintergrund: Wenn eine Ausgabe 
geliefert wird, ist eine positive Antwort eingetroffen; wenn diese Ausgabe nicht gekommen ist, muss man noch warten oder sie kommt nie. Es gibt semi-entscheidbare Mengen, deren Komplement nicht semi-entscheidbar ist.
Inhaltsverzeichnis |
[Bearbeiten] Berechenbare Mengen
In der Literatur taucht gelegentlich der Begriff der berechenbaren Menge auf. Dieser Begriff wird uneinheitlich verwendet. Es können damit entscheidbare Mengen oder semi-entscheidbare Mengen gemeint sein.
[Bearbeiten] Eigenschaften
- Eine Menge ist genau dann semi-entscheidbar, wenn sie rekursiv aufzählbar ist.
- Eine Menge ist genau dann semi-entscheidbar, wenn sie der Wertebereich einer berechenbaren Funktion ist.
- Eine formale Sprache ist genau dann semi-entscheidbar, wenn sie Typ-0 ist.
- Eine Menge ist genau dann entscheidbar, wenn sie und ihr Komplement semi-entscheidbar sind.
[Bearbeiten] Beispiele
- Das Halteproblem der Turingmaschinen ist semi-entscheidbar, denn man kann die gegebene Turingmaschine mit der gegebenen Eingabe laufen lassen und nach seiner Terminierung ausgeben. Das Komplement des Halteproblems ist nicht semi-entscheidbar.
- Das Äquivalenzproblem der Turingmaschinen ist nicht semi-entscheidbar. Auch das Komplement des Äquivalenzproblems ist nicht semi-entscheidbar.
