Specker-Folge

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Eine Specker-Folge. Die n. Ziffer von xn+k ist 4 wenn die Berechnung von {n}(n) nach k Schritten hält; sonst 3.

In der Berechenbarkeitstheorie ist die Specker-Folge eine berechenbare, monoton wachsende, beschränkte Folge von rationalen Zahlen, deren Supremum keine berechenbare reelle Zahl ist. Das erste Beispiel einer solchen Folge wurde 1949 von Ernst Specker konstruiert.

Die Existenz von Specker-Folgen hat Konsequenzen für die berechenbare Analysis. Die Tatsache, dass es solche Folgen gibt, bedeutet, dass die Klasse der berechenbaren reellen Zahlen nicht die aus der reellen Analysis bekannte Supremumseigenschaft aufweist, selbst dann, wenn man sich dabei auf berechenbare Folgen beschränkt. Ein üblicher Weg, dieses Problem zu lösen, ist es, nur berechenbare Folgen versehen mit einem berechenbaren Konvergenzmodul zu betrachten. Keine Specker-Folge hat einen berechenbaren Konvergenzmodul, das bedeutet, jeder Konvergenzmodul einer Specker-Folge wächst schneller als jede berechenbare Funktion, sonst ließe sich auf berechenbare Weise abschätzen, nach wie vielen Folgengliedern die ersten n Stellen feststehen, und damit wäre das Supremum eine berechenbare reelle Zahl.

Die Supremumseigenschaft wurde auch im Bereich der reversen Mathematik untersucht, wo ihre genaue Stärke bestimmt wurde. In der Sprache der Disziplin ausgedrückt ist die Supremumseigenschaft äquivalent zu ACA0 über RCA0.

Verletzung der Supremumseigenschaft[Bearbeiten]

Da jede rationale Zahl berechenbar ist und die Vervollständigung der rationalen Zahlen bekanntlich genau die Menge der reellen Zahlen ist, die berechenbaren reellen Zahlen als abzählbare Menge aber eine echte Teilmenge der reellen Zahlen bilden, können die berechenbaren reellen Zahlen nicht vollständig sein. Da besagte Supremumseigenschaft in metrischen, separablen, geordneten Räumen und somit jedem Unterraum der reellen Zahlen äquivalent zur Ordnungsvollständigkeit und somit zur Vollständigkeit ist, können die berechenbaren reellen Zahlen nicht die Supremumseigenschaft erfüllen. Naheliegend wäre nun, sich auf berechenbare Folgen berechenbarer Zahlen zu beschränken.

Konstruktion[Bearbeiten]

Die Existenz einer Specker-Folge besagt darüber hinaus, dass die Supremumseigenschaft bereits verletzt ist, wenn man sich auf berechenbare Folgen beschränkt. Die folgende Konstruktion wurde von Kushner (1984) beschrieben. Sei A eine rekursiv aufzählbare, aber nicht entscheidbare Menge natürlicher Zahlen, und sei (ai) eine berechenbare Aufzählung von A ohne Wiederholung. Eine Folge (qn) von rationalen Zahlen sei definiert durch die Regel

q_n = \sum_{i = 0}^n 2^{-a_i - 1}.

Offensichtlich ist jedes qn nichtnegativ und rational, und die Folge (qn) wächst monoton. Außerdem ist es möglich, jedes qn gegen die Reihe

\sum_{i = 0}^\infty 2^{-i-1} = 1

abzuschätzen, da (ai) keine Wiederholung enthält. Daher ist die Folge (qn) durch 1 beschränkt. Klassischerweise bedeutet dies, dass (qn) ein Supremum x besitzt.

Es wurde gezeigt, dass x keine berechenbare reelle Zahl ist. Der Beweis verwendet einen bestimmten Fakt über berechenbare reelle Zahlen: Wenn x berechenbar wäre, dann gäbe es eine berechenbare Funktion r(n) so, dass |qj - qi| < 1/n für alle i,j > r(n). Um r zu berechnen, vergleiche man die Binärexpansion von x mit der Binärexpansion von qi für immer größere Werte von i. Die Definition von qi führt dazu, dass jedes Mal, wenn i um 1 größer wird, eine binäre Ziffer von 0 zu 1 wechselt. Also gibt es ein n so, dass ein hinreichend großes Anfangsstück von x durch qn dergestalt festgelegt ist, dass keine weitere Binärziffer in diesem Stück auf 1 wechseln kann, was zu einer Abschätzung der Distanz zwischen qi und qj füri,j > n führt.

Wenn irgendeine solche Funktion r berechenbar wäre, würde dies auf folgende Weise zu einem Entscheidungsverfahren für A führen. Gegeben eine Eingabe k, berechne man r(2k+1). Wenn k in der Folge (ai) auftauchen würde, würde dies eine Erhöhung von (qi) um 2-k-1 verursachen, aber dies kann nicht passieren, sobald alle Elemente von (qi) nicht weiter als 2-k-1 voneinander entfernt sind. Wenn also k in einem ai aufgezählt wird, muss es um den Wert von i kleiner sein als r(2k+1). Es bleibt eine endliche Zahl von möglichen Orten, wo k aufgezählt werden könnte. Um das Entscheidungsverfahren zu vervollständigen, prüfe man diese endlich vielen Stellen in berechenbarer Weise und gebe 0 oder 1 aus, je nachdem, ob k gefunden wird oder nicht.

Einzelnachweise[Bearbeiten]

  • Douglas Bridges und Fred Richman. Varieties of Constructive Mathematics, Oxford, 1987.
  • B.A. Kushner (1984), Lectures on constructive mathematical analysis, American Mathematical Society, Translations of Mathematical Monographs v. 60.
  • Jakob G. Simonsen (2005), "Specker sequences revisited", Mathematical Logic Quarterly, v. 51, pp. 532-540. doi:10.1002/malq.200410048
  • S. Simpson (1999), Subsystems of second-order arithmetic, Springer.
  • E. Specker (1949), "Nicht konstruktiv beweisbare Sätze der Analysis" Journal of Symbolic Logic, v. 14, pp. 145–158.