Berechenbare Menge

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 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:

  • Berechenbare Funktion — In der Berechenbarkeitstheorie nennt man eine Funktion berechenbar, wenn es einen Algorithmus gibt, der die Funktion berechnet. Die Funktion, die ein Algorithmus berechnet, ist gegeben durch die Ausgabe, mit der der Algorithmus auf eine Eingabe… …   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

  • Abzählbare Menge — In der Mengenlehre wird eine Menge A als abzählbar unendlich bezeichnet, wenn sie die gleiche Mächtigkeit hat wie die Menge der natürlichen Zahlen . Dies bedeutet, dass es eine Bijektion zwischen A und der Menge der natürlichen Zahlen gibt, die… …   Deutsch Wikipedia

  • 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 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

  • Königslemma — Das Lemma von König oder Königslemma ist ein Theorem der Graphentheorie von Dénes Kőnig (1936). Die Berechenbarkeit des Lemmas wurde gründlich in der Mathematischen Logik erforscht. Dénes Kőnig wird korrekterweise mit Doppelakut geschrieben. Das… …   Deutsch Wikipedia

  • Lemma von König — Das Lemma von König oder Königslemma ist ein Theorem der Graphentheorie von Dénes Kőnig (1936). Die Berechenbarkeit des Lemmas wurde gründlich in der Mathematischen Logik erforscht. Dénes Kőnig wird korrekterweise mit Doppelakut geschrieben. Das… …   Deutsch Wikipedia

  • Berechenbar — In der Berechenbarkeitstheorie nennt man eine Funktion berechenbar, wenn es einen Algorithmus gibt, der die Funktion berechnet. Die Funktion, die ein Algorithmus berechnet, ist gegeben durch die Ausgabe, mit der der Algorithmus auf eine Eingabe… …   Deutsch Wikipedia

  • Turing-Berechenbarkeit — In der Berechenbarkeitstheorie nennt man eine Funktion berechenbar, wenn es einen Algorithmus gibt, der die Funktion berechnet. Die Funktion, die ein Algorithmus berechnet, ist gegeben durch die Ausgabe, mit der der Algorithmus auf eine Eingabe… …   Deutsch Wikipedia

  • Berechenbarkeit — In der Berechenbarkeitstheorie nennt man eine Funktion berechenbar, wenn es einen Algorithmus gibt, der die Funktion berechnet. Die Funktion, die ein Algorithmus berechnet, ist gegeben durch die Ausgabe, mit der der Algorithmus auf eine Eingabe… …   Deutsch Wikipedia

Share the article and excerpts

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