Wie lange braucht ein Zufallsgenerator um den C++ Quellcode für "Hello World!" zu generieren?

[Hat Dawkins Recht?]

Angenommen wir haben einen perfekten Zufallsgenerator und lassen diesen einen fortwährenden Datenstrom generieren, mit dem Ziel, daß er irgendwann in dem Datenstrom einen Abschnitt generiert hat, der dem C++ Quellcode für die Ausgabe von "Hello World!" entspricht.

So sollte unser Quellcode aussehen.
Wir sind sogar so freundlich und erlauben es dem Quellcode in einer Hochsprache geschrieben zu sein und Bibliotheken zu nutzen, ohne den Maschinencode direkt selbst schreiben zu müssen:

#include <iostream>

using namespace std;

int main()
{
  cout << "Hello World!" << endl;
  return 0;
}

Gibt man dem Zufallgsgenerator genug Rechenzeit, so ist es ja nicht unmöglich, daß er irgendwann den korrekten Code ausspuckt. Richtig?
Die Grundgröße für den kleinsten nicht teilbaren Bereich des Datenstroms ist übrigens das Byte.
D.h. der kleinste nicht trennbare Teil des Datenstroms kann eine von 256 Möglichkeiten annehmen.

Da nicht benötigte Leerzeichen weggelassen werden dürfen, besteht obiger Quellcode genaugenommen aus einem Datenstrom aus 90 Char werten bzw. 90 Bytes
und läßt sich so noch kompilieren (obiger Code dient nur der besseren Lesbarkeit):

#include <iostream>
using namespace std;int main(){cout<<"Hello World!"<<endl;return 0;}

Wie viele Bytes in Folge muß der Zufallsgenerator im Mittel generieren, bist er obigen Quellcode in korrekter Reihenfolge ausspuckt?

Wieviele Jahre würde ein moderne Core2Duo E6300 dazu im Mittel benötigen?

[Hat Dawkings Recht?]

Dann noch eine weitere erschwerende Annahme für die Aufgabe (obiges ist Aufgabe A).

Wir erweiteren die Frage mit der Bedingung, daß der Zufallsgenerator
den Datenstrom in Teile, deren Länge nach dem Zufallsprinzip variieren darf, auftrennen muß, die er dann in einzelne C++ Dateien speichern und
zu compilieren versuchen muß.

Wieviele mögliche Dateien variabler Länge muß der Zufallsgenerator anlegen, bis
er genau eine Datei mit dem Inhalt des obigen "Hello World!" Programms generiert hat?

Wieviele Jahre würde oben genannter Rechner für diese Aufgabe benötigen?

Dann noch etwas, wir gehen von der Annahme aus, daß dem Rechner unendlich viel Speicherplatz zur Verfügung steht und die Datenmenge trotz nur 64 Bit CPU verwaltet werden kann.

[Hat Dawkins Recht?]

Hat Dawkings Recht? schrieb:

Wieviele mögliche Dateien variabler Länge muß der Zufallsgenerator anlegen, bis
er genau eine Datei mit dem Inhalt des obigen "Hello World!" Programms generiert hat?

Auch hier gilt wieder "im Mittel".

[Elektronix]

Wenns ein Zufallsgenerator ist, kann er zufällig den String schon beim ersten Versuch generieren.
Wie lange er dafür braucht, hängt vom Zufall ab- und natürlich von der Taktrate des Rechners und vom OS :p .

[life]

zu a): Es gibt 256^90 viele Möglichkeiten, wobei genau eine richtig ist. Somit braucht er etwa 256^90 viele Versuche. Schafft der PC 10^9 viele Überprüfungen pro sec, dann braucht er etwa 174900185917744396839444704700371442022073601886260538841237614035267595364796290592613521116939643196149952230826228146139239732089317995927927178492867409123625336636770038146671169983108561 Milliarden Jahre, bis er Hello World generiert hat.

[qwdfb]

Hat Dawkins Recht? schrieb:

...

was hat das ganze mit deinem namen zu tun.

[C++ Forumbot]

Dieser Thread wurde von Moderator/in rüdiger aus dem Forum Rund um die Programmierung in das Forum Mathematik verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

[makkurona]

@life: Stimmt so nicht. Da es heir um einen Zufallsgenerator geht.
Es kann sein, das das richtige Ergebnis gleich beim ersten versuch kommt, es kann aber auch sein, dass es nie kommt.
Es hat eifnach nur eine gewisse Wahrcsheinlichkeit, dass es kommt, mehr nicht.

Du kannst also nur ausrechnen, mit welcher Wahrscheinlichkeit es in einem Zeitraum auftaucht. (:

[Gast 2]

life schrieb:

zu a): Es gibt 256^90 viele Möglichkeiten, wobei genau eine richtig ist. Somit braucht er etwa 256^90 viele Versuche.

So eine Formel wäre zwar beim Lotto richtig, da dort die Reihenfolge egal ist,
aber hier gilt das nicht, denn es muß ja auch die Reihenfolge korrekt sein.

[Gregor]

Gast 2 schrieb:

life schrieb:

zu a): Es gibt 256^90 viele Möglichkeiten, wobei genau eine richtig ist. Somit braucht er etwa 256^90 viele Versuche.

So eine Formel wäre zwar beim Lotto richtig, da dort die Reihenfolge egal ist,
aber hier gilt das nicht, denn es muß ja auch die Reihenfolge korrekt sein.

So eine Formel wäre im Lotto nicht richtig. Im Lotto hast Du $\left( \begin{array}{c} 49 \\ 6 \end{array}\right)$ Möglichkeiten. (Ohne die Superzahl jetzt)

[Heinzelotto]

life schrieb:

zu a): Es gibt 256^90 viele Möglichkeiten, wobei genau eine richtig ist. Somit braucht er etwa 256^90 viele Versuche. Schafft der PC 10^9 viele Überprüfungen pro sec, dann braucht er etwa 174900185917744396839444704700371442022073601886260538841237614035267595364796290592613521116939643196149952230826228146139239732089317995927927178492867409123625336636770038146671169983108561 Milliarden Jahre, bis er Hello World generiert hat.

es kommt statistisch gesehen nach durchschnittlich der hälfte der jahre, die du angegeben hast, wenn deine anzahl die maximale anzahl ist. Nach soviel Jahren, wie du sie angegeben hast, schafft er er 100%ig, da da alle Möglichkeiten durchprobiert wurden.

[Michael E.]

Heinzelotto schrieb:

es kommt statistisch gesehen nach durchschnittlich der hälfte der jahre, die du angegeben hast, wenn deine anzahl die maximale anzahl ist. Nach soviel Jahren, wie du sie angegeben hast, schafft er er 100%ig, da da alle Möglichkeiten durchprobiert wurden.

Dann wäre der Zufallsgenerator aber nicht sehr zufällig, da er einfach nur eine permutierte Folge ausgeben würde.

BTW: Schon mal dran gedacht, dass in 91 Zeichen bereits zwei, in 92 Zeichen drei... Möglichkeiten enthalten sind?

[Jester]

Heinzelotto schrieb:

Nach soviel Jahren, wie du sie angegeben hast, schafft er er 100%ig, da da alle Möglichkeiten durchprobiert wurden.

glaubst du auch daran, dass man nur 6 mal würfeln muß um garantiert auf jeden fall mal eine 6 gewürfelt zu haben?

[life]

Ich habe den Erwartungswert einer geometrischen verteilten Zufallsvariable ausgerechnet (http://de.wikipedia.org/wiki/Geometrische_Verteilung). Also die erwartete Anzahl der (Bernoulli-)Versuche (hier: zufälliges Programm der Länge 90 Bytes schreiben), die nötig sind für einen Erfolg (hier: Hello-World Programm). Siehe auch Jesters Würfelbeispiel...

[sothis_]

Jester schrieb:

Heinzelotto schrieb:

Nach soviel Jahren, wie du sie angegeben hast, schafft er er 100%ig, da da alle Möglichkeiten durchprobiert wurden.

glaubst du auch daran, dass man nur 6 mal würfeln muß um garantiert auf jeden fall mal eine 6 gewürfelt zu haben?

chuck norris kann das

[Gast 2]

Gregor schrieb:

Gast 2 schrieb:

life schrieb:

zu a): Es gibt 256^90 viele Möglichkeiten, wobei genau eine richtig ist. Somit braucht er etwa 256^90 viele Versuche.

So eine Formel wäre zwar beim Lotto richtig, da dort die Reihenfolge egal ist,
aber hier gilt das nicht, denn es muß ja auch die Reihenfolge korrekt sein.

So eine Formel wäre im Lotto nicht richtig. Im Lotto hast Du $\left( \begin{array}{c} 49 \\ 6 \end{array}\right)$ Möglichkeiten. (Ohne die Superzahl jetzt)

Oh doch, denn Formel != Zahlenwerte in der Formel!

[Michael E.]

Und da $\left( \begin{array}{c} 256 \\ 90 \end{array}\right) = 256^{90}$, sind alle glücklich

Edit: Plödes LaTeX.

[Heinzelotto]

Jester schrieb:

Heinzelotto schrieb:

Nach soviel Jahren, wie du sie angegeben hast, schafft er er 100%ig, da da alle Möglichkeiten durchprobiert wurden.

glaubst du auch daran, dass man nur 6 mal würfeln muß um garantiert auf jeden fall mal eine 6 gewürfelt zu haben?

mann, bin ich blöd, ich habe irgendwie verpeilt, dass das ein zufallsgenerator ist

[Jester]

Michael E. schrieb:

Und da $\left( \begin{array}{c} 256 \\ 90 \end{array}\right) = 256^{90}$, sind alle glücklich

Edit: Plödes LaTeX.

hu? was geht denn hier? wenn du schon unsinn schreibst mach wenigstens ne clownsnase dazu.

[rüdiger]

http://en.wikipedia.org/wiki/Infinite_monkey_theorem