www.wikidata.de-de.nina.az
Als rekursiv aufzahlbare Menge auch semi entscheidbare Menge positiv semi entscheidbare Menge halb entscheidbare Menge berechenbar aufzahlbare Menge kurz r e c e wird in der Berechenbarkeitstheorie eine Menge von naturlichen Zahlen bezeichnet wenn es einen Algorithmus gibt der die Elemente dieser Menge aufzahlt Aquivalent ist diese Charakterisierung Es gibt einen Algorithmus der 1 ausgibt wann immer die Eingabe ein Element der betreffenden Menge ist und auf anderen Eingaben nie halt Jede entscheidbare Menge ist rekursiv aufzahlbar aber es gibt rekursiv aufzahlbare Mengen die nicht entscheidbar sind Mengen von anderen Objekten als naturlichen Zahlen heissen rekursiv aufzahlbar wenn sie sich durch Godelisierung in eine rekursiv aufzahlbare Menge naturlicher Zahlen ubersetzen lasst In der Literatur taucht gelegentlich der Begriff der berechenbaren Menge auf Dieser Begriff wird uneinheitlich verwendet Es konnen damit entscheidbare Mengen oder rekursiv aufzahlbare Mengen gemeint sein Inhaltsverzeichnis 1 Formale Definition 2 Aquivalenzen zur Definition 3 Eigenschaften 4 Beispiele 5 LiteraturFormale Definition BearbeitenFormal werden rekursiv aufzahlbare Mengen meist durch eine der folgenden zueinander aquivalenten Definitionen charakterisiert Rekursive AufzahlbarkeitEine Menge M N displaystyle M subseteq mathbb N nbsp heisse rekursiv aufzahlbar falls M displaystyle M emptyset nbsp leer ist oder es eine totale berechenbare Funktion N M displaystyle mathbb N to M nbsp gibt deren Bild gerade M displaystyle M nbsp ist Semi EntscheidbarkeitDie Menge M displaystyle M nbsp heisse semi entscheidbar wenn die partielle charakteristische Funktion x M N 1 displaystyle chi M colon mathbb N rightsquigarrow 1 nbsp von M displaystyle M nbsp berechenbar ist Aquivalenzen zur Definition BearbeitenFolgende Satze sind untereinander aquivalent M displaystyle M nbsp ist rekursiv aufzahlbar M displaystyle M nbsp ist semi entscheidbar M displaystyle M nbsp ist vom Chomsky Typ 0 M displaystyle M nbsp ist die Menge aller Berechnungsergebnisse einer Turingmaschine M displaystyle M nbsp ist Definitionsbereich einer berechenbaren Funktion M displaystyle M nbsp ist Bildmenge einer berechenbaren Funktion M displaystyle M nbsp ist endlich oder Wertebereich einer injektiven berechenbaren Funktion M displaystyle M nbsp ist Bildmenge einer primitiv rekursiven Funktion oder die leere Menge M displaystyle M nbsp liegt in der Klasse S 1 0 displaystyle Sigma 1 0 nbsp der arithmetischen Hierarchie M displaystyle M nbsp lasst sich many one auf das Halteproblem reduzieren Es gibt eine entscheidbare Menge B N 2 displaystyle B subseteq mathbb N 2 nbsp fur die gilt x M y x y B displaystyle x in M Leftrightarrow exists y colon x y in B nbsp Eigenschaften BearbeitenJede entscheidbare Menge ist rekursiv aufzahlbar aber es gibt rekursiv aufzahlbare Mengen die nicht entscheidbar sind Eine Menge ist genau dann entscheidbar wenn sie und ihr Komplement rekursiv aufzahlbar sind Jede endliche Menge ist rekursiv aufzahlbar Jede rekursiv aufzahlbare Menge ist abzahlbar aber nicht alle abzahlbaren Mengen sind rekursiv aufzahlbar Jede unendliche rekursiv aufzahlbare Menge besitzt Teilmengen die nicht rekursiv aufzahlbar sind Der Schnitt von endlich vielen rekursiv aufzahlbaren Mengen ist rekursiv aufzahlbar die Vereinigung einer rekursiv aufzahlbaren Menge von rekursiv aufzahlbaren Mengen ist rekursiv aufzahlbar Es gibt rekursiv aufzahlbare Mengen deren Komplement nicht rekursiv aufzahlbar ist Eine partielle Funktion ist genau dann berechenbar wenn ihr Graph rekursiv aufzahlbar ist Beispiele BearbeitenDie Menge der Paare der Form Programm Eingabe mit der Eigenschaft das Programm halt mit der Eingabe ist rekursiv aufzahlbar Diese Menge wird auch Universelle Sprache genannt Damit ist das Halteproblem der Turingmaschinen semi entscheidbar denn man kann die gegebene Turingmaschine mit der gegebenen Eingabe laufen lassen und nach ihrer Terminierung 1 ausgeben Das Komplement des Halteproblems ist nicht semi entscheidbar Die Selbstanwendbarkeit ist rekursiv aufzahlbar In obigem Beispiel beschranken wir uns auf die Eingaben die dem jeweiligen Programm entsprechen Das Aquivalenzproblem der Turingmaschinen ist nicht semi entscheidbar Auch das Komplement des Aquivalenzproblems ist nicht semi entscheidbar Die Werte der Busy Beaver Funktion sind nicht rekursiv aufzahlbar Literatur BearbeitenHartley Rogers Theory of recursive functions and effective computability McGraw Hill 1967 Abgerufen von https de wikipedia org w index php title Rekursiv aufzahlbare Menge amp oldid 228600263