www.wikidata.de-de.nina.az

Indexmenge Berechenbarkeitstheorie Eine Indexmenge von engl index set auch semantische Menge 1 genannt ist in der Berech

Indexmenge (Berechenbarkeitstheorie)

Eine Indexmenge (von engl. index set), auch semantische Menge genannt, ist in der Berechenbarkeitstheorie eine Vereinigung von Gödelnummern berechenbarer Funktionen, die alle Indizes von Funktionen einer bestimmten Klasse enthalten.

Definition Bearbeiten

Sei eine effektive Nummerierung aller partiell berechenbarer Funktionen. Eine Menge heiße semantisch falls gilt:

Falls also zwei Indizes die gleiche Funktion beschreiben, liegen entweder beide in oder keiner von ihnen.

Dabei heißen zwei partielle Funktionen gleich, wenn sie an denselben Stellen (un)definiert sind und wann immer sie definiert sind, auch stets das gleiche Ergebnis liefern.

Charakterisierung Bearbeiten

Es bezeichne die Gesamtheit aller partiell berechenbaren Funktionen, zu jeder Funktionsklasse gibt es genau eine Indexmenge, die die Nummern von Funktionen aus enthält.

Umgekehrt lässt sich zu jeder semantischen Menge auch eine entsprechende eindeutige Klasse von Funktionen finden.

Das bedeutet, dass eine Indexmenge durch die semantischen Eigenschaften der Funktionen aus vollständig bestimmt ist, daraus ergibt sich auch die Bezeichnung.

Beispiele Bearbeiten

Die folgenden Mengen sind Indexmengen:

Diese Mengen sind keine Indexmengen:

Eigenschaften Bearbeiten

  • Jede nicht-leere Indexmenge besitzt eine unendliche rekursiv aufzählbare Teilmenge (und ist daher selbst unendlich), dies folgt aus dem Padding-Lemma.
  • Komplemente sowie beliebige Schnitte und Vereinigungen semantischer Mengen sind wieder semantisch.
  • Indexmengen sind dann und nur dann entscheidbar, wenn sie trivial sind (d. h. oder ganz ), dies ist der Satz von Rice.
  • Eine Menge ist genau dann many-one-reduzierbar auf eine Indexmenge, wenn sie auf diese one-one-reduzierbar ist, alle semantische Mengen sind daher Zylinder.

Literatur Bearbeiten

  • H. Rogers jr.: Theory of recursive functions and effective computability. 2nd ed., 3rd printing (1992), MIT Press, Cambridge MA, ISBN 0-262-68052-1

Einzelnachweise Bearbeiten

  1. Bez. bspw. bei T. Kötzing: Berechenbarkeitstheorie. Vorlesung an der Friedrich-Schiller-Universität Jena im Sommersemester 2013.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Eine Indexmenge von engl index set auch semantische Menge 1 genannt ist in der Berechenbarkeitstheorie eine Vereinigung von Godelnummern berechenbarer Funktionen die alle Indizes von Funktionen einer bestimmten Klasse enthalten Inhaltsverzeichnis 1 Definition 2 Charakterisierung 3 Beispiele 4 Eigenschaften 5 Literatur 6 EinzelnachweiseDefinition BearbeitenSei f n n N displaystyle lbrace varphi n rbrace n in mathbb N nbsp eine effektive Nummerierung aller partiell berechenbarer Funktionen Eine Menge A N displaystyle A subseteq mathbb N nbsp heisse semantisch falls gilt n m N f n f m n A m A displaystyle forall n m in mathbb N colon varphi n varphi m land n in A Rightarrow m in A nbsp Falls also zwei Indizes die gleiche Funktion beschreiben liegen entweder beide in A displaystyle A nbsp oder keiner von ihnen Dabei heissen zwei partielle Funktionen gleich wenn sie an denselben Stellen un definiert sind und wann immer sie definiert sind auch stets das gleiche Ergebnis liefern Charakterisierung BearbeitenEs bezeichne P displaystyle mathcal P nbsp die Gesamtheit aller partiell berechenbaren Funktionen zu jeder Funktionsklasse S P displaystyle mathcal S subseteq mathcal P nbsp gibt es genau eine Indexmenge die die Nummern von Funktionen aus S displaystyle mathcal S nbsp enthalt Umgekehrt lasst sich zu jeder semantischen Menge auch eine entsprechende eindeutige Klasse von Funktionen finden Das bedeutet dass eine Indexmenge durch die semantischen Eigenschaften der Funktionen aus S displaystyle mathcal S nbsp vollstandig bestimmt ist daraus ergibt sich auch die Bezeichnung Beispiele BearbeitenDie folgenden Mengen sind Indexmengen das e displaystyle varepsilon nbsp Halteproblem H 0 n f n 0 displaystyle H 0 n mid varphi n 0 downarrow nbsp die Menge T O T A L n k f n k displaystyle TOTAL n mid forall k colon varphi n k downarrow nbsp der Godelnummern aller uberall definierten berechenbaren FunktionenDiese Mengen sind keine Indexmengen das allgemeine Halteproblem H n k f n k displaystyle H langle n k rangle mid varphi n k downarrow nbsp mit N 2 N displaystyle langle cdot cdot rangle mathbb N 2 rightarrow mathbb N nbsp Die Elemente dieser Menge definieren keine Funktionen Es kann zum Beispiel f n k displaystyle varphi langle n k rangle uparrow nbsp gelten dd das spezielle Halteproblem K n f n n displaystyle K n mid varphi n n downarrow nbsp f n f n n n K displaystyle varphi n varphi n nRightarrow n n in K nbsp da im Allgemeinen f n n f n n displaystyle varphi n n downarrow nLeftrightarrow varphi n n downarrow nbsp Zum Beispiel fur die Funktion welche nur an der Stelle n displaystyle n nbsp definiert ist dd Eigenschaften BearbeitenJede nicht leere Indexmenge besitzt eine unendliche rekursiv aufzahlbare Teilmenge und ist daher selbst unendlich dies folgt aus dem Padding Lemma Komplemente sowie beliebige Schnitte und Vereinigungen semantischer Mengen sind wieder semantisch Das System der Indexmengen bildet also sowohl eine s Algebra als auch eine Topologie auf N displaystyle mathbb N nbsp Indexmengen sind dann und nur dann entscheidbar wenn sie trivial sind d h displaystyle emptyset nbsp oder ganz N displaystyle mathbb N nbsp dies ist der Satz von Rice Eine Menge ist genau dann many one reduzierbar auf eine Indexmenge wenn sie auf diese one one reduzierbar ist alle semantische Mengen sind daher Zylinder Literatur BearbeitenH Rogers jr Theory of recursive functions and effective computability 2nd ed 3rd printing 1992 MIT Press Cambridge MA ISBN 0 262 68052 1Einzelnachweise Bearbeiten Bez bspw bei T Kotzing Berechenbarkeitstheorie Vorlesung an der Friedrich Schiller Universitat Jena im Sommersemester 2013 Abgerufen von https de wikipedia org w index php title Indexmenge Berechenbarkeitstheorie amp oldid 183548803