Berechenbare Ordnung

Berechenbare Ordnungen bezeichnen in der theoretischen Informatik, genauer in der Berechenbarkeitstheorie, bestimmte entscheidbare Relationen. Sie bilden den Ausgangspunkt für semi-berechenbare Mengen sowie für berechenbare Ordinalzahlen.

Definition

Es sei $\leq _{R}\,\subseteq \mathbb {N} \times \mathbb {N}$ eine Totalordnung auf der Menge der natürlichen Zahlen.

Die Relation $\leq _{R}$ heißt berechenbare Ordnung, falls die Funktion $(x;y)\mapsto {\begin{cases}1,&{\text{falls }}x\leq _{R}y,\\0,&{\text{sonst}}\end{cases}}$ total berechenbar ist.

In anderen Worten ist eine berechenbare Ordnung eine zweistellige, totale, reflexive, transitive, antisymmetrische und entscheidbare Relation auf den natürlichen Zahlen.

Grundsätzlich könnte man berechenbare Ordnungen auch auf einem anderen Grundbereich betrachten. Ist dieser allerdings endlich, so ist jede Totalordnung berechenbar; ist er überabzählbar, so ist es keine. Für abzählbar unendliche Grundbereiche gibt es dagegen stets eine Bijektion von den natürlichen Zahlen, entlang derer man die Ordnung auf $\mathbb {N}$ zurückziehen kann.

Beispiele und Gegenbeispiele

• Die natürliche Anordnung von $\mathbb {N}$ ist berechenbar.
• Die Ordnung $1<3<5<\cdots <0<2<4<\cdots$ ist ebenfalls berechenbar.
• Bezeichne $K=\{x_{1}<x_{2}<\cdots \}$ das spezielle Halteproblem und ${\overline {K}}=\{y_{1}<y_{2}<\cdots \}$ sein Komplement, dann ist $x_{1}<x_{2}<\cdots <y_{1}<y_{2}<\cdots \$ nicht berechenbar.

Diese Beispiele zeigen, dass Ordnungsisomorphie und Berechenbarkeit unabhängig voneinander sind. Insbesondere erhält ein Ordnungsautomorphismus nur dann die Berechenbarkeit, wenn er selbst berechenbar ist.

Semi-berechenbare Mengen

Eine Menge $A\subseteq \mathbb {N}$ heiße semi-berechenbar (von engl. semirecursive), falls es eine total berechenbare Funktion $f$ gibt, so dass $\forall x;y\colon f(x;y)\in \{x;y\}$ und $\forall x;y\colon \{x;y\}\cap A\neq \emptyset \Rightarrow f(x;y)\in A$ gilt.

Anschaulich gesprochen berechnet $f$ also für je zwei natürliche Zahlen diejenige, die eher in $A$ liegt. Das bedeutet, sobald mindestens eine der beiden Eingaben tatsächlich in $A$ liegt, wird auch ein Element von $A$ zurückgegeben.

Hinweis: Der Begriff der semi-berechenbaren Menge darf nicht mit dem der semi-entscheidbaren Menge verwechselt werden.

Es ergibt sich nun die folgende Charakterisierung:

Eine Menge $A$ ist genau dann semi-berechenbar, wenn sie ein Anfangsstück einer berechenbaren Ordnung ist.

Außerdem gelten folgende Eigenschaften:

• Entscheidbare Mengen sind semi-berechenbar, die Umkehrung gilt im Allgemeinen nicht.
• Komplemente semi-berechenbarer Mengen sind ebenfalls wieder semi-berechenbar.
• Ist $A$ many-one-reduzierbar auf eine semi-berechenbare Menge $B$, $A\preceq _{m}B$, so ist auch $A$ semi-berechenbar.
• Jeder Turinggrad enthält eine semi-berechenbare Menge. Tatsächlich gibt es sogar in jedem $tt$-Grad eine solche, vgl. Reduktion.
• Einfache semi-berechenbare Mengen sind hypereinfach.

Literatur

• H. Rogers jr.: Theory of recursive functions and effective computability. 2nd ed., 1987, MIT Press, Cambridge MA, ISBN 0-262-68052-1.
• P. Odifreddi: Classical Recursion Theory. North-Holland, 1989, ISBN 0-444-87295-7.