Zufällige Objekte zu betrachten ist in der Mathematik eine immer populärer werdende Methode. Klassisches Beispiel ist die Existenz transzendenter Zahlen. Es ist sehr schwer, transzendente Zahlen zu konstruieren. Es ist aber nicht schwer zu beweisen, dass eine zufällige Zahl mit Wahrscheinlichkeit 1 transzendent ist. Ähnlich ist es schwer, Expander-Graphen (stabile Netzwerke) zu konstruieren. Es ist einfacher zu beweisen, dass ein zufälliger Graph mit Wahrscheinlichkeit 1 ein Expander ist. Die Theorie der Zufallsgraphen ist seit Erdös und Renyi ein eigenes Forschungsgebiet. Auch in der Theorie der endlichen Gruppen sind Zufallsbetrachtungen von Nutzen. Und es wurde bewiesen, dass zufällige (unendliche) Gruppen mit überwältigender Wahrscheinlichkeit hyperbolisch sind und als Rand die Mengerkurve haben.

Das Opernhaus Wuppertal präsentiert heute Abend (19:30 Uhr) die Übertragung dieses Prinzips in die Kunst, nämlich eine aus Versatzstücken 64 rechtefrei verfügbarer Opernwerke durch Auswürfeln zusammengesetzte Oper. Was damit wohl bewiesen werden wird?

Der Sender DF Kultur hatte (aus diesem Anlaß?) heute eine einstündige Sendung über die Rolle des Zufalls in der Kunst und anderswo: Der geplante Kontrollverlust.

Kommentare (13)

  1. #1 Stefan Köppel
    Bad Kissingen
    4. Februar 2019

    Bzgl. transzendenter Zahlen hätte ich eine Frage.
    Die Mächtigkeit der Menge transzendenter Zahlen ist ja bekanntlich überabzählbar.
    Nun gibt es aber transzendente Zahlen wie PI und e, die mithilfe eines endlichen Algorithmus beliebig angenähert werden können.
    Die Menge aller endlichen Algoithmen ist aber abzählbar.
    Daraus folgt doch, daß nur eine Teilmenge der transzendenten Zahlen überabzählbar ist, oder?
    Hat die Menge aller “nicht durch endliche Algorithmen approximierbaren” zahlen einen Namen?

  2. #2 rolak
    5. Februar 2019

    moin Stefan,
    1) was soll bitte ein ‘endlicher Algorithmus’ sein? Endliche Laufzeit (also aka ‘terminierender Algorithmus’) oder ‘#syntax-token<∞’ (also jeder) oder etwas anderes?
    2) was meinst Du mit ‘beliebig angenähert’? Gibt es für ‘vorher ein beliebiges ε≪1 festlegen’ nichtterminierende Approximations-Algorithmen?
    3) was soll das ‘nur’ in ‘nur eine Teilmenge .. überabzählbar’? Wenn eine Teilmenge überabzählbar ist, ists die komplette doch auch…

  3. #3 Stefan Köppel
    Schweinfurt
    5. Februar 2019

    1.Mit endlichem Algorithmus meine ich eine endliche Anzahl an Sourcecode-Zeilen.
    2.Dachte nur in die Richtung, daß bei unendlich langer laufzeit die annäherung besser wird. Die Argumentation funktioniert aber auch mit: “Eine zahl die mit endlicher Zahl an Worten beschrieben werden kann”.
    3. Unglücklich formuliert. Meinte, daß PI und e zu einer Teilmenge der Transzendenten Zahlen gehören, die abzählbar ist, weil sie aus approximierbaren Zahlen besteht.

  4. #4 rolak
    5. Februar 2019

    1) Das trifft, wie schon erwähnt, auf jeden Algorithmus zu, Stefan. Dpedia formuliert

    Algorithmen bestehen aus endlich vielen, wohldefinierten Einzelschritten

    2+3) Soll das etwa heißen, Du setzt die von Dir immer noch nicht mit verständlichem Sinn erfüllte Eigenschaft ‘approximierbar’ mit ‘mit endlicher Wortzahl [eindeutig] beschreibbar’ gleich? Letzteres ist selbstverständlich für (alle Elemente überabzählbarer Mengen) per def unmöglich.

    Falls Du mit ‘approximierbar’ allerdings meinen solltest ‘für ein gegebenes D∈ℕ auf D Stellen in der Dezimaldarstellung genau darstellbar’, ist dies überhaupt kein Problem – falls Dir die zwar endliche, doch ggfs ziemlich lange Laufzeit nicht stört und Du ausreichend Speicherplatz (und Daten) zur Verfügung stellst. Algorithmen können nämlich nicht nur irgendwelche Ziffernfolgen ‘aus dem Nichts’ generieren, sondern auch Eingaben verarbeiten – und die erfreulich simpel umzusetzende Funktion id() ist auch einer.

  5. #5 Stefan Köppel
    Schweinfurt
    5. Februar 2019

    Oh. Daß Algorithmus per definition endlich ist, hatte ich tatsächlich nicht auf dem Schirm. Ok. Ich versuch nochmal anders zu verdeutlichen worauf ich hinaus will, wenn du noch soviel Geduld hast.

    Die Menge aller möglichen Algoritmen, ist abzählbar.
    Die Menge der transzendentalen Zahlen ist überabzählbar.
    Es lässt sich ein Algorithmus finden, der nie stoppt und nach und nach alle Stellen einer Transzendenten Zahl auspuckt.
    Ich mach eine Abbildung von den Algorithmen zu ihren passenden Transzendenten Zahlen.

    Das genügt doch um eine abzählbare Teilmenge der Transzendenten zu basteln. Ich zähle sie einfach anhand ihrer generierenden Algorithmen.

  6. #6 michael
    5. Februar 2019

    > Das genügt doch um eine abzählbare Teilmenge der Transzendenten zu basteln. Ich zähle sie einfach anhand ihrer generierenden Algorithmen.

    Das kann man einfacher haben: {1*pi,2*pi,3*pi, … } ist eine abzaehbare Menge von transzendente Zahlen

    > Es lässt sich ein Algorithmus finden, der nie stoppt und nach und nach alle Stellen einer Transzendenten Zahl auspuckt.

    Ein Algorithmus, der die Stellen eine transzendenten Zahl nacheinander ausgibt, kann auch nicht stoppen, da er unendlich viele Stellen ausgeben muss.

    Wenn allerdings gemeint ist, ob es eine transzendente Zahl gibt, deren Dezimalstellen nicht durch einen Algorithmus berechnet werden können, dann ist die Antwort wohl ‘ja’.

  7. #7 Stefan Köppel
    Schweinfurt
    5. Februar 2019

    > Wenn allerdings gemeint ist, ob es eine transzendente Zahl gibt, deren Dezimalstellen nicht durch einen Algorithmus berechnet werden können, dann ist die Antwort wohl ‘ja’

    Genau das meinte ich.
    Wenn man nun alle transzendenten Zahlen, die durch einen Algorithmus berechnet werden können in eine Menge packt, stellt man fest, daß pi, e in der abzählbaren stecken.
    Meine Urspungsfrage zielte in die Richtung, ob diese beiden Klassen von Transzendenten Zahlen einen Namen haben.

  8. #8 rolak
    6. Februar 2019

    ..ob es eine transzendente Zahl gibt, deren Dezimalstellen nicht durch einen Algorithmus berechnet werden können, dann ist die Antwort wohl ‘ja’

    So allgemein formuliert ist die Antwort eindeutig ‘nein’, michael, da mußt Du schon sehr stark einschränken á la ‘Algorithmen, die keine Eingaben verarbeiten’. Denn das schon erwähnte id(), vielleicht mal in der etwas ausgeschmückten Form (auch wenn auch ohne das Lametta schon reichlich gerechnet werden würde)

    loop{
     ziffer.read.input();
     ziffer++;
     ziffer- -;
     ziffer.write.output();
     };

    kann selbstverständlich alle Ziffern jeder transzendenten Zahl berechnen, wenn sie ihm nur in der korrekten Reihenfolge gefüttert werden.
    Ebenso selbstverständlich brauchts keine Abbruchbedingung, just keep on typing ;•)

  9. #9 Stefan Köppel
    Schweinfurt
    6. Februar 2019

    hmm.
    interessant. aber ist Algo + Input noch deterministisch, wenn man Wahlfreiheit hat?
    Ein nicht-deterministischer Algorithmus hat auch keine Probleme Transzendene Zahlen der überabzählbaren Klasse zu produzieren:
    loop:{
    ziffer=random(9);
    ziffer.write.output();
    }

  10. #10 michael
    6. Februar 2019

    > jeder transzendenten Zahl berechnen, wenn sie ihm nur in der korrekten Reihenfolge gefüttert werden.

    Und wie kommst du an die einzugebenden Ziffern ran ? Göttliche Eingebung oder berechnest Du sie irgendwie?

  11. #11 rolak
    7. Februar 2019

    Wie? Göttlich?

    Ersteres ist aufgrund der Fragestellung (s.o.) völlig unwesentlich, michael, da es nur um den Algorithmus ging, zweiteres ist mit extrem hoher Wahrscheinlichkeit ausschließbar.

    deterministisch, wenn .. Wahlfreiheit?

    Da existiert keine Wahlfreiheit, Stefan, weil eine transzendente Zahl herauskommen soll – ist aber auch, wie im ersten Teil schon gesagt, irrelevant.
    Dein Algorithmus ist übrigens (aufgrund der üblichen Implementierung von random() als Pseudozufallsgenerator) keineswegs nichtdeterministisch; produziert ausschließlich ganze Zahlen (das Geheimnis meines A.s ist die Definition von ‘ziffer’ als Objekt über charset [‘0′..’9′,’,’]); bzw bei gedachtem, implizitem, führenden Komma periodische Zahlen zwischen Null und Eins.

  12. #12 rolak
    7. Februar 2019

    btt: Wie es bei Opern funktionieren mag, kann ich mir nicht so recht vorstellen, doch bereits vor längerem (~Mitte 80er) erlebte ich in D’dorf ein Konzert (jaaa, da gabs mehrere, weiß ich) in(?) der RSH, bei dem ein eher kleines Ensemble ~spontan (es wurde (mir) nicht klar, wer wann welche Zahl hochhalten durfte und was genau das bewirkte) zwischen deutlich unterschiedlichen Fragmenten wechselte bis darüber improvisierte. Das klang mir zwar sehr schräg, aber erfreulich angenehm.

  13. #13 Stefan Köppel
    Schweinfurt
    7. Februar 2019

    Eine führene 0. hab ich genauso impliziert wie eine echte random funktion. daher nicht deterministisch.

    Wie der Input bei deinem Algo zustande kommt ist sogar sehr wichtig. Wenn in dem Kopf des eingebenden ein deterministischer algo läuft zur bestimmung der nächsten nachkommastelle kann keine transzendente zahl der überabzählbaren klasse rauskommen.
    Da die kombination von berechenbarem Input und berechenbarem Algo wieder berechenbar ist.
    Transzendente Zahlen der überabzählbaren Klasse sind aber nicht berechenbar. (jedenfalls nicht mit endlichen programmen einer deterministischen Touringmaschine)