Direkt zum Inhalt

Lexikon der Mathematik: produktive Menge

eine Menge A, für die es eine total berechenbare Funktion f gibt, so daß für alle x gilt: \begin{eqnarray}{W}_{x}\subseteq A\Rightarrow f(f)\in A-{W}_{x}.\end{eqnarray}

Hierbei ist W1, W2, … eine Aufzählung der rekursiv aufzählbaren Mengen. Eine solche Aufzählung erhält man durch Arithmetisierung aller Turing-Maschinen.

Eine produktive Menge ist auf „konstruktive“ Weise nicht rekursiv aufzählbar: Zu jeder rekursiv aufzählbaren Teilmenge von A gibt es effektiv ein Gegenbeispiel dazu, daß A identisch mit dieser rekursiv aufzählbaren Menge ist.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos