Semi-entscheidbare Menge

Semi-entscheidbare Menge

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 f:M\rightsquigarrow \mathbb B definiert durch

f(x) = \begin{cases}\top, & \mbox{falls } x\in A,\\ \mbox{undefiniert}, & \mbox{sonst,}\end{cases}

berechenbar ist. Die Menge M muss dazu gödelisierbar sein. In der Theorie setzt man zum einfacheren Vergleich direkt M=\mathbb{N} oder M = {0,1} * voraus. Im letzteren Fall hat man die Menge als das Wortproblem einer formalen Sprache dargestellt.

Hintergrund: Wenn eine Ausgabe \top 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

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.

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.

Beispiele

  1. Das Halteproblem der Turingmaschinen ist semi-entscheidbar, denn man kann die gegebene Turingmaschine mit der gegebenen Eingabe laufen lassen und nach seiner Terminierung \top ausgeben. Das Komplement des Halteproblems ist nicht semi-entscheidbar.
  2. Das Äquivalenzproblem der Turingmaschinen ist nicht semi-entscheidbar. Auch das Komplement des Äquivalenzproblems ist nicht semi-entscheidbar.

Siehe auch


Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Entscheidbare Menge — Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), 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… …   Deutsch Wikipedia

  • Rekursiv entscheidbare Menge — Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), 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… …   Deutsch Wikipedia

  • Semi-entscheidbare Sprache — Eine rekursiv aufzählbare Sprache oder semientscheidbare Sprache L ist dadurch definiert, dass es eine Turingmaschine gibt, die alle Wörter aus L akzeptiert, aber keine Wörter, die nicht in L liegen. Im Unterschied zu rekursiven Sprachen oder… …   Deutsch Wikipedia

  • Semi-Entscheidbarkeit — 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… …   Deutsch Wikipedia

  • Semi-entscheidbar — 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… …   Deutsch Wikipedia

  • Berechenbare Menge — 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… …   Deutsch Wikipedia

  • Rekursiv aufzählbare Menge — 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… …   Deutsch Wikipedia

  • Aufzählbare Menge — Die rekursive Aufzählbarkeit ist ein Begriff aus der Berechenbarkeitstheorie. Er gibt Aufschluss darüber, ob sich die Elemente einer vorgegebenen Menge schrittweise von einem Computer erzeugen lassen. Inhaltsverzeichnis 1 Definition 2… …   Deutsch Wikipedia

  • Entscheidbarkeit — Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), 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… …   Deutsch Wikipedia

  • Entscheidungsproblem — Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), 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… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”