Omega / Super-Omega Zahl?

Anonym · 14. März 2001 um 15:46

Hallo!

Wie erklärt man einem Mathematik-Laien was eine Omega oder eine Super-Omega Zahl ist!
(siehe http://www.newscientist.com/features/features.jsp?id…)

Ciao
Catmad

Martin · 14. März 2001 um 19:50

Hi Catmad,

die Zahl Omega ist ein überraschendes Ergebnis aus einer Reihe von Untersuchungen, die der Mathematiker G. Chaitin im Zusammenhang mit einem berühmten mathematischen Problem durchgeführt hat.

Angenommen, Du hast eine Gleichung, die zwei (oder mehr) Größen x und y miteinander verknüpft, z. B.

x + y^2 = 1

Wenn x und y auch nicht-ganzzahlige Werte annehmen dürfen, dann gibt es unendlich viele Paare (x, y), die die Gleichung erfüllen, z. B. x = 3/4 und y = 1/2. Interessant wird es nun, wenn wir nur nach den positiven ganzzahligen Lösungen einer solchen Gleichung fragen. Probleme dieser Kategorie heißen „diophantisch“ (nach dem Griechen Diophantus, einem großen Algebraiker des Altertums (um 250 n. Chr.)). Diophantische Gleichungen haben mehr als eine mögliche Lösung. Im obigen einfachen Beispiel sind (0, 1) und (1, 0) die einzigen Lösungen.

Wir verallgemeinern das Beispiel nun etwas, indem wir auf der rechten Seite die „1“ durch ein „Q“ ersetzen, und Q jeden ganzzahligen Wert, also 1, 2, 3 usw. annehmen lassen. Und schließlich wollen wir noch eine weitere Verallgemeinerung vornehmen, indem wir diophantische Gleichungen mit N Variablen betrachten statt nur mit zweien.

Nun kann man sich verschiedene Fragen stellen – eine wäre z. B., ob eine Gleichung dieser Form im allgemeinen (d. h. für jedes Q) eine ganzzahlige Lösung hat. Die Frage, auf die Chaitin eine Antwort suchte, war eine etwas andere, und zwar diese: „Hat eine gegebene diophantische Gleichung für ein bestimmtes Q = 1, 2, 3… endlich oder unendlich viele verschiedene Lösungen?“

Was Chaitin nun herausfand, war etwas ziemlich erstaunliches. Er konnte nämlich zeigen, daß seine Frage prinzipiell nicht beantwortet werden kann! Die Antwort ist „zufällig“ in dem Sinn, daß ihre Lösung mehr Information braucht, als in der Arithmetik enthalten ist. Die Frage gehört damit zur Klasse der nicht berechenbaren Probleme (wozu ebenfalls zählen: „Hält dieses Computerprogramm mit diesem Input jemals an?“ und „Gibt es ein kleineres Computerprogramm als dieses, das exakt dasselbe tut?“).

Chaitin ging nun hin, und bastelte sich aus der Nicht-Berechenbarkeit der Antwort auf die Frage, ob eine diophantische Gleichung im allgmeinen endlich oder unendlich viele Lösungen hat, eine Zahl. Dazu tat er folgendes: Man fängt bei Q=1 an und schreibt eine „1“ auf, wenn die betrachtete diophantische Gleichung endlich viele Lösungen hat; wenn nicht, schreibt man eine „0“ hin. Erhöht man Q nun fortlaufend um 1 und notiert immer entsprechend eine Null oder eine Eins, dann erhält man eine unendlich lange binäre Folge, deren Anfang z. B. so aussehen könnte:

000101100110010101010110101…

Chaitin bewies, daß diese Folge die Fähigkeiten jedes Computerprogramms übersteigt. Zwar kann ein Programm eine endliche Anzahl von Stellen berechnen, aber die obere Grenze der Stellenzahl hängt von seiner eigenen Komplexität ab. Dies ist der fundamentale Unterschied zu einem berechenbaren Problem wie z. B. „Primzahlen“: Ein und dasselbe „kleine“ Programm kann die 5. oder 20. oder 100000. oder n-te, wobei n beliebig groß sein darf, Primzahl berechnen – genug Speicherplatz und Rechenzeit vorausgesetzt (diese Größen haben nichts mit der Komplexität des Programms zu tun). Bei den Chaitinschen Folgen ist das anders: Jedes „kleine“ Programm kann immer nur eine „kleine“ Anzahl der Stellen berechnen. Will man mehr Stellen, so braucht man ein größeres Programm.

Anders ausgedrückt: Eine binäre Folge wie z. B.

„0000000000 …[weitere 999980 mal „0“]… 0000000000“

ist nicht so komplex, wie sie lang ist. Ein Progamm, das nichts weiter tut, als 1000000 mal das Bit „0“ auszudrucken, braucht nicht 1000000 Bits groß zu sein, sondern „kommt mit viel weniger aus“. Oder noch anders ausgedrückt: Eine Sequenz von 1000000 aufeinanderfolgenden „0“-Bits ist komprimierbar. Hier muß man sich jedoch klarmachen, daß z. B. die unendliche Folge der Nachkommastellen von pi ebenfalls komprimierbar ist. Die Ziffern sind hier zwar „zufällig“ in dem Sinn, daß sie ausnahmslos jeden Zufallsgeneratortest bestehen (man hat das sogar tatsächlich überprüft), aber das ist nicht das „richtige“ Kriterium. Das richtige Kriterium ist, daß ein geeignetes Programm endlicher Komplexität in der Lage ist, so viele Stellen zu berechnen, wie immer gewünscht werden. Dies ist bei den Chaitinschen Folgen nicht der Fall – sie sind nicht komprimierbar, weil sie alle die Eigenschaft haben, so komplex wie lang zu sein.

Chaitin machte nun aus der unendlich langen Folge eine ordentliche Zahl, indem er einfach eine Null und ein Komma davorsetzte. Das ergibt eine binäre Zahl, die immer zwischen Null und Eins liegt (aber nie gleich Null oder gleich Eins ist). Diese Zahl nannte er „Omega“. Aus der obigen Beispielfolge würde man also die Omegazahl

_O_ = 0.000101100110010101010110101…

erhalten. Es gibt natürlich unendlich viele Omegazahlen, je nachdem, welche diophantische Gleichung zugrundeliegt. Es wurde gezeigt, daß _O_ folgende überraschende Bedeutung hat. Ordnet man einer diophantischen Gleichung in bestimmter (abstrakter) Weise ein Computerprogramm zu, und startet dieses Programm mit einem zufällig gewählten Input, dann gibt das zugehörige _O_ die Wahrscheinlichkeit dafür an, daß das Programm nach einer endlichen Anzahl von Schritten terminiert (_O_ = 0[1] würde bedeuten, daß das Programm nie[immer] aufhört).

Das _O_-Konzept steht in sehr engem Zusammenhang mit dem Gödelschen Unvollständigkeitssatz, also mit der Theorie über unentscheidbare Aussagen in formalen Systemen. Es wurde gezeigt, daß jede der unendlich lange Zahlenfolgen, die ein _O_ ausmachen, einer unentscheidbaren Aussage in der Arithmetik entspricht. Weitere Gebiete, wo die _O_-Zahlen an diversen Stellen auftauchen, sind die Komplexitätstheorie und die Chaostheorie.

Damit ist natürlich noch längst nicht alles gesagt, aber ich hoffe, Du konntest zumindest einen kleinen Einblick gewinnen.

Mit freundlichem Gruß
Martin

PS: Über Super-Omega-Zahlen weiß ich leider auch nichts.

Lutz_Lehmann · 14. März 2001 um 19:43

Es ist Sensationsjournalismus at its best
Die praktische Aussage dieses Artikels bzw. der Theorie ist das lang bekannte Prinzip von der Erhaltung der Schwierigkeit: Je allgemeiner eine Aussage wird, desto komplizierter ist sie zu beweisen, Spezialfaelle mit staerkeren Annahmen sind einfacher zu beweisen, decken aber evtl. interessante Faelle nicht ab.
Nimm einen abstrakten Computer (Turing-Maschine) mit einem einfachen Befehlssatz (ueblicherweise um die 7 Befehle, siehe z.B. CoreWars), unendlich Speicher, Ein- und Ausgabedatei ohne Beschraenkung.

Jedes (endliche?) Programm hat eine Binaerkodierung, mit etwas Aufwand laesst es sich einrichten, dass jeder (endlichen?) Bitfolge ein Programm entspricht.

Mache daraus eine bijektive Abbildung auf das Einheitsintervall [0,1)
Versehe das Intervall [0,1) mit einer Dichte, z.B. Gleichverteilung. Oder denk Dir eine Wahrscheinlichkeitsverteilung der endlichen Bitfolgen aus.

Ordne jeder Zahl nun eine 1 zu, wenn das kodierte Programm die Ende-Anweisung erreicht, Null sonst

Zeige, dass diese Funktion messbar ist (nur bei unendlichen Folgen)

Berechne den Erwartungswert dieser Funktion. Nenne diesen Omega.

Super-Omega gehoert noch weiter in den Bereich mathematischer Esoterik (nett darueber nachzudenken, praktisch nutzlos). Warum? Weil selbst „primitive“ Probleme wie das Finden aller Loesungen eines nichtlinearen Gleichungssystems doppelt exponentielle Komplexitaet haben. Also Speicheranforderungen in der Groesse d^(n^2) bits fuer Polynome in n Variablen vom Grad d. Setze d=n=10, nimm pro bit ein Atom, berechne die Masse des Speichers und staune.

Ciao Lutz

PS: Und ja, es mag mal huebsche Anwendungen dieser Theorie geben, etwa im Zusammenhang mit der Sicherheit von Verschluesselungen.

PPS: Ich habe die genaue Theorie nicht gelesen, nur den Zeitungsartikel in mir verstaendlichen Begriffe interpretiert. Die wirkliche Theorie kann wesentlich verwickelter sein.

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

Lutz_Lehmann · 14. März 2001 um 20:26

Dies ist der fundamentale Unterschied zu einem
berechenbaren Problem wie z. B. „Primzahlen“: Ein und dasselbe
„kleine“ Programm kann die 5. oder 20. oder 100000. oder
n-te, wobei n beliebig groß sein darf, Primzahl
berechnen - genug Speicherplatz und Rechenzeit vorausgesetzt
(diese Größen haben nichts mit der Komplexität des Programms
zu tun).

komprimierbar. Hier muß man sich jedoch klarmachen, daß
z. B. die unendliche Folge der Nachkommastellen von pi
ebenfalls komprimierbar ist. Die Ziffern sind hier zwar
„zufällig“ in dem Sinn, daß sie ausnahmslos jeden
Zufallsgeneratortest bestehen (man hat das sogar tatsächlich
überprüft), aber das ist nicht das „richtige“ Kriterium. Das
richtige Kriterium ist, daß ein geeignetes Programm
endlicher Komplexität in der Lage ist, so viele Stellen
zu berechnen, wie immer gewünscht werden.

Um es mal komplizierter zu machen: Diese Aussagen stimmen nicht. Jedes realistische und damit endlich beschreibbare Modell der Bitdarstellung von ganzen Zahlen kann immer nur eine endliche Anzahl ganzer Zahlen abdecken. Um ueber Maschinenzahlen hinauszugehen benutzt man BigInts (endliche Folgen von Maschinenzahlen), jedoch wird die Stellenzahl durch eine Maschinenzahl repraesentiert (und das reicht bei heutigen Computern). Will man groessere Zahlen darstellen, muss auch die Stellenzahl ein BigInt sein, dessen Stellenzahl codiert werden muss, usw. Jetzt kann die Hoehe der so entstehenden Hierarchie variabel gestaltet werden, jedoch muss auch diese Hoehe kodiert werden, …

Und bei jedem Qualit"atssprung ist ein neues, groesseres Programm faellig.

D.h. das Komprimierungskonzept muss wenigstens auf logarithmisch oder polynomial wachsende Programmgroesse erweitert werden.

Andererseits duerften BigInts mit BigInts als Stellenzahl (und deren Stellenzahl als 32 oder 64-Bit-Wort) die Moeglichkeiten eines jeden auf der Erde jemals realisierbaren Computers uebersteigen.

Ciao Lutz

Martin · 16. März 2001 um 17:10

Hallo Lutz!

Um es mal komplizierter zu machen: Diese Aussagen stimmen nicht.

Dann will ich die Sache mal wieder einfach machen, und zeigen, daß die Aussagen doch stimmen.

Jedes realistische und damit endlich beschreibbare
Modell der Bitdarstellung von ganzen Zahlen kann immer nur
eine endliche Anzahl ganzer Zahlen abdecken. Um ueber
Maschinenzahlen hinauszugehen benutzt man BigInts (endliche
Folgen von Maschinenzahlen), jedoch wird die Stellenzahl durch
eine Maschinenzahl repraesentiert (und das reicht bei heutigen
Computern). Will man groessere Zahlen darstellen, muss auch
die Stellenzahl ein BigInt sein, dessen Stellenzahl codiert
werden muss, usw. Jetzt kann die Hoehe der so entstehenden
Hierarchie variabel gestaltet werden, jedoch muss auch diese
Hoehe kodiert werden, …

Ich finde Deine Gedanken sehr interessant (ohne Ironie!), muß aber einwenden, daß das Konzept, das Du zugrundelegst, zu sehr an dasjenige angelehnt ist, nach dem die heutigen real existierenden Computer konstruiert sind.

Eines der wesentlichen Merkmale der heutigen Computer ist, daß sie mit einem RAM arbeiten, einem „Speicher mit wahlfreiem Zugriff“ (RAM = „random access memory“). Das bedeutet, daß die Speicherzellen durchnumeriert sind, und es Register auf dem Prozessor gibt, die zur Adressierung der Speicherzellen dienen (z. B. den „program counter“, der auf die gerade auszuführende Maschinenanweisung zeigt). Da so ein Register nur eine endliche Breite haben kann (z. B. 32 Bit), ist dadurch z. B. automatisch der maximal adressierbare Arbeitsspeicher begrenzt (z. B. auf 4 GByte).

Nun ist aber ein RAM nicht das einzig mögliche Modell eines Speichers. Das „klassische Modell“ der Turingmaschine arbeitet mit einer internen „Übergangstabelle“ endlicher Größe als Programm, und verwendet als Arbeitsspeicher ein nach beiden Seiten hin unendliches Band, also einen sequentiellen Speicher (für Pingelige: ja, es gibt auch Varianten mit einem Band, das nur nach einer Seite hin unendlich ist, aber das spielt hier keine Rolle). Der Clou dabei ist, daß die von Dir angesprochenen Adressierungsbeschränkungen hier von Haus aus nicht auftreten. Die Turingmaschine kann sich nämlich gar nicht irgendwelche Adressen von Zahlen merken, die in einem RAM-mäßig organisierten Speicher untergebracht sind, und sie braucht es auch nicht, weil sie sich die Zahl, die es gerade braucht, auf dem Band sucht (suchen kann/suchen muß). Damit hat sie auch kein Problem, denn sie muß nur den Schreibkopf solange vorwärtsbewegen, bis der Kopf über dem Beginn der zu verarbeitenden Zahl (oder einem entsprechenden Kennungssymbol oder etc.) steht.

Beispiel: Eine Turingmaschine soll die Aufgabe erfüllen, eine beliebige, „eingegebene“ Zahl zu verzehnfachen. Das Alphabet der Maschine soll aus den Ziffern „0“ bis „9“ und der „Endemarkierung“ „.“ bestehen.

Die „Input-Zahl“ soll 349815 sein. Auf dem Band steht folglich:

 3 4 9 8 1 5 .

und der Schreib-Lesekopf steht über dem ersten Zeichen, also der „3“.

Wie lautet das interne „Programm“ der Maschine? Nun, so:

1. Bewege den Kopf solange nach rechts, bis Du auf das Zeichen "." triffst.
2. Drucke das Zeichen "0".
3. Bewege den Kopf noch genau eine Position weiter nach rechts.
4. Drucke das Zeichen "."
5. Halte an.

Nachdem die Maschine fertig ist, enthält das Band den korrekten „Output“

 3 4 9 8 1 5 0 .

Was dieses Einfachbeispiel verdeutlichen soll, ist, daß die Maschine mit ihrem Mini-Programm ihre Aufgabe bei _jeder noch so großen Input-Zahl erfüllen kann, ohne daß an ihrem Programm jemals etwas geändert werden muß.

Es läßt sich nun zeigen, daß es für jedes berechenbare Problem ein endliches, festes Programm gibt, mit dem eine Turingmaschine die Aufgabe lösen kann, ohne daß ihr Programm jemals in irgendeiner Form „angepaßt“ werden muß, z. B. weil die Input-Zahlen „zu groß“ gewählt werden. Wie kompliziert dieses Programm im Einzelfall möglicherweise sein muß, ist hier unerheblich. Es muß in jedem Fall immer nur endlich groß sein, wobei seine „Größe“ dann das Maß für die Komplexität des Programms ist (ach ja, damit bei anderen Lesern keine Verwirrung aufkommt: Diese Größe „Komplexität“ hat nichts mit der Zeitkomplexität eines Algorithmus’ à la "Quicksort hat „n log n“ zu tun).

In diesem Zusammenhang ist es vielleicht noch interessant, darauf hinzuweisen, daß man Programmiersprachen konstruieren kann, die vollständig ohne das Konzept der „Variablen“ auskommen. Ein Vertreter so einer Sprache, der tatsächlich implementiert wurde, ist „Unlambda“. „Unlambda“ kennt weder „Integers“ noch Arrays noch Stacks noch Sprunganweisungen noch Schleifen noch Bedingungen und ist trotzdem vollständig Turing-äquivalent, erlaubt also die Berechnung ausnahmslos jedes Problems, das überhaupt berechenbar ist! (Um die Idee von „Unlambda“ kurz zu skizzieren: Es gibt nichts außer Funktionen – die Funktion ist das einzige Objekt, das manipuliert wird. Jede Funktion bekommt eine Funktion als Parameter übergeben und liefert eine Funktion zurück. Das mathematische Äquivalent ist das sogenannte „Lambda-Kalkül“, wobei die Sprache allerdings gar nicht über das „Lambda“ selbst verfügt – daher „Unlambda“. Die Sprache wurde wie dazu entworfen, das Programmieren extrem diffizil und verzwickt zu machen).

Und bei jedem Qualit"atssprung ist ein neues, groesseres
Programm faellig.

D.h. das Komprimierungskonzept muss wenigstens auf
logarithmisch oder polynomial wachsende Programmgroesse
erweitert werden.

Für eine nach dem RAM-Speichermodell arbeitende Maschine halte ich Deinen Einwand für berechtigt; im allgemeinen, „theoretischen“ Fall (Turing-Maschine) hat er dagegen gar keine Grundlage.

Andererseits duerften BigInts mit BigInts als Stellenzahl (und
deren Stellenzahl als 32 oder 64-Bit-Wort) die Moeglichkeiten
eines jeden auf der Erde jemals realisierbaren Computers
uebersteigen.

In diesem Punkt stimme ich Dir vollumfänglich zu !

Mit freundlichem Gruß
Martin

PS: Hier der Link zu „Unlambda“, falls es jemanden interessiert:
http://www.eleves.ens.fr:8080/home/madore/programs/u…_