Berechenbare Ordinalzahl

Berechenbare Ordinalzahlen sind die Ordnungstypen berechenbarer Wohlordnungen. Sie werden in der theoretischen Informatik, genauer in der Berechenbarkeitstheorie, behandelt. Die Menge der berechenbaren Ordinalzahlen bildet ein abzählbares Anfangsstück der natürlichen Anordnung aller Ordinalzahlen.

Definition

Eine Ordinalzahl $\alpha$ heißt berechenbar, falls es eine berechenbare Ordnung $(M;\leq _{M})$ gibt, die zu $\alpha$ ordnungsisomorph ist.

Notwendig ist $\leq _{M}$ dann eine Wohlordnung auf einer Teilmenge $M\subseteq \mathbb {N}$ der natürlichen Zahlen. Allerdings ist nicht jede solche Wohlordnung berechenbar. Sogar Ordnungen die isomorph zu einer berechenbaren Ordinalzahl sind, müssen nicht selbst berechenbar sein (s. Beispiele).

Beispiele

• Alle endlichen Ordinalzahlen sind berechenbar.
• Die natürliche Ordnung der Menge $\mathbb {N}$ ist entscheidbar, daher ist die Ordinalzahl $\omega$ berechenbar.
• Die Wohlordnung $1<3<5<\cdots <0<2<4<\cdots \$ ist berechenbar und daher auch die Ordinalzahl $\omega \cdot 2$.
• Bezeichne $K=\{x_{1}<x_{2}<\cdots \}$ das spezielle Halteproblem und ${\overline {K}}=\{y_{1}<y_{2}<\cdots \}$ sein Komplement, dann hat die Ordnung $x_{1}<x_{2}<\cdots <y_{1}<y_{2}<\cdots \$ zwar ebenfalls den Ordnungstyp $\omega \cdot 2$, ist jedoch nicht berechenbar.

Church-Kleene-Ordinalzahl

Es gibt nur abzählbar viele entscheidbare Relationen, daher haben die berechenbaren Ordinalzahlen ein höchstens abzählbares Supremum, die Church-Kleene-Ordinalzahl $\omega _{1}^{CK}$. Sie ist benannt nach Alonzo Church und Stephen Cole Kleene, die sich als erste mit rekursiven Notationssystemen für Ordinalzahlen beschäftigten. Wegen $\omega <\omega _{1}^{CK}$ (s. o.) ist die Church-Kleene-Ordinalzahl tatsächlich abzählbar unendlich.

Es gilt folgende Charakterisierung:

Eine Ordinalzahl ist genau dann berechenbar, wenn sie echt kleiner als $\omega _{1}^{CK}$ ist.

Eine Ordinalzahl $\alpha$ ist weiterhin genau dann berechenbar, wenn sie konstruktiv ist. Das heißt, wenn es ein berechenbares Notationssystem gibt, dessen Bild $\alpha$ enthält. Nicht jede abzählbare Ordinalzahl ist auch berechenbar, insbesondere $\omega _{1}^{CK}$ ist es nicht.

Literatur

• H. Rogers, Jr.: Theory of Recursive Functions and Effective Computability. MIT Press, Cambridge, MA 1987, ISBN 978-0-262-68052-3.
• P. Odifreddi: Classical Recursion Theory. North-Holland, Amsterdam 1989, ISBN 0-444-87295-7.