Rekursive Isomorphie ist in der Berechenbarkeitstheorie eine Äquivalenzrelation auf Mengen natürlicher Zahlen.

Definition

Bearbeiten

Mengen   natürlicher Zahlen heißen rekursiv isomorph  , falls es eine totale berechenbare Bijektion   gibt, so dass   gilt.

Nummerierungen   einer (höchstens) abzählbaren Menge   heißen rekursiv isomorph, falls es eine ebensolche Bijektion   mit   gibt.

Die Abbildung   heißt dann rekursiver Isomorphismus.

Eigenschaften

Bearbeiten
  • Rekursive Isomorphie ist eine Äquivalenzrelation auf der Potenzmenge   der natürlichen Zahlen.
  • Ist   ein rekursiver Isomorphismus, so ist notwendig auch seine Umkehrfunktion   berechenbar.
  • Eine Menge ist genau dann rekursiv isomorph zum Halteproblem  , wenn sie kreativ ist.

Isomorphiesatz von Myhill

Bearbeiten

Folgender Satz von John Myhill liefert eine Charakterisierung des Begriffes der rekursiven Isomorphie:

Seien   erneut Mengen natürlicher Zahlen, so gilt:

 

Zwei Mengen sind also genau dann rekursiv isomorph, wenn sie one-one-äquivalent sind.

Der Beweis zu diesem Satz ist eine effektive Variante des Beweises des Satzes von Schröder-Bernstein.

In der Theorie der Turing-Grade lässt sich mit Hilfe des Isomorphiesatzes eine weitere wichtige Äquivalenz folgern:

 

Zwei Mengen befinden sich also genau dann im gleichen Turing-Grad, wenn ihre jeweiligen Turing-Sprünge rekursiv isomorph sind.

Literatur

Bearbeiten
  • J. Myhill: Creative Sets. In: Zeitschrift für Mathematische Logik und Grundlagen der Mathematik Vol. 1 (1955), S. 97–108.
  • H. Rogers: Theory of recursive function and effective computability (2nd ed.). 1987, MIT Press, Cambridge, MA.