Ja wir sind beim Kapitel Nummer 7. Thema des Kapitels ist das millionste Computerprogramm. Was ist jetzt das? Wo ist das millionste? Wo ist denn das erste Computerprogramm überhaupt? Wie sieht denn das aus? Gut also mit solchen Fragen werden wir uns befassen und da gibt es interessante Zusammenhänge im

Bezug zu den klassischen Konzepten der theoretischen Informatik, nämlich was ist Aufzählen und was ist Abzählen? Was ist der Unterschied zwischen Aufzählen und Abzählen? Wann ist was aufzählbar und wann ist was abzählbar? Theoretische Informatik 1 oder 2?

Nee, hat damit jetzt nichts zu tun. Ja, was ist Aufzählen? Ja, ja, ja, ein bisschen später mit.

Abzählbar kennen Sie aus der Mathematik? Abzählbare Menge. Ja, also man kann den Objekten einer Menge der Reihe nach natürliche Zahlen zuordnen.

Das ist abzählbar. Also es gibt eine bi-jektive Abbildung zwischen der Menge N und der abzählbaren Menge, die man jetzt gerade unter Beobachtung hat. Was ist jetzt Aufzählbar? Ja, maschinell zu nennen. Dann stimmt es fast.

Also Aufzählbar heißt, es gibt ein Algorithmus, der die Elemente der Menge der Reihe nach hinschreibt. Die dürfen dabei auch mehrfach vorkommen,

aber der Algorithmus lässt man ihm genügend Zeit. Die Menge kann ja unendlich sein. Lässt man ihm genügend Zeit, blättert er alle Elemente aus der Menge entsprechend hin. Das ist Aufzählbar. Also Abzählbar ist irgendwie eine Möglichkeit. Es existiert eine Zuordnung und Aufzählbar

heißt, da gehört der zugehörige Algorithmus dazu. Das ist der große Unterschied. Also Aufzählbar und Abzählbar, das sind die Begriffe, die sollten sie auseinanderhalten können. Das sind eben zwei unterschiedliche Dinge und die Mathematik kümmert sich, glaube ich,

nicht um Aufzählbarkeit. Das ist für die relativ uninteressant, auch nicht viel über Abzählbarkeit, glaube ich. Aber die Begriffe stehen da nicht im Mittelpunkt. Aber in der Informatik spielt das schon eine Rolle, weil wir die Begriffe von Aufzählbarkeit, Entscheidbarkeit, Unentscheidbarkeit, die bilden da so ein Dreigestirn. Wann ist was aufzählbar, wann ist

was entscheidbar? Wie hängt das zusammen? Was ist aufzählbar und in Zusammenhang mit Entscheidbar? Hat das irgendeinen Zusammenhang? Ja. Wobei halten? Nee, das ist nicht lange her. Ja gut, in heutigen Zeiträumen heißt

es ja alles lange her, was eine Klausur her ist. Ja, also Entscheidbar heißt die Menge und ihr Kompliment sind aufzählbar. Erinnern

Sie sich noch dran? Eine Menge heißt entscheidbar, eine Menge M heißt entscheidbar, wenn M und M quer aufzählbar sind. Und das kann man sich leicht klar machen. Die Turing-Maschine, wir argumentieren ja denken sie einfach Maschine. Entscheidbar bedeutet ja, sie geben

ein Element vor und eine Menge und nach einer gewissen Zeit sagt ihnen die Maschine, dieses Element gehört zu der Menge oder dieses Element gehört nicht zu der Menge, diese Entscheidung kann die Maschine treffen. So und dann stoppt sie natürlich, wenn sie die Entscheidung getroffen haben. So und den Zusammenhang zwischen Aufzählbarkeit und Entscheidbarkeit kann man sich

gut klar machen, wenn man Aufzählbarkeit der Menge und Aufzählbarkeit des Kompliments der Menge hat, dann hat man ja auch zwei Maschinen. Die eine zählt die Menge auf und die andere zählt das Kompliment der Menge auf. Schreibt die Elemente sozusagen von M beziehungsweise von M quer irgendwie der Reihe nach hinten in irgendeiner Weise. So und die Entscheidbarkeit ergibt sich dann

natürlich, ich kann aus den beiden Maschinen, die jetzt beide Mengen aufzählen, M und M quer, da kann ich eben eine Maschine konstruieren, die für ein beliebiges Element sagt, ob das in der Menge oder in der M quer ist. Ich lasse einfach die beiden Maschinen parallel laufen. So und warte so lange,

bis das Element auftaucht, entweder bei der einen oder bei der anderen. Und da wo es als erstes auftaucht, dann kann ich sofort sagen, es ist in der Menge drin und bei dem anderen kann ich sagen, es ist nicht in der Menge drin. Das ist der Zusammenhang. Deswegen sagt man, eine Menge ist entscheidbar, wenn M und M quer aufzählbar ist. Das ist sogar eine

Äquivalenz zwischen diesen beiden Dingen. So, der Zusammenhang, Sie ändern sich an die Beweistechnik der Nichtberechenbarkeit. Nochmal aus Grundlagen der Programmierung 1, da war das so, zähle die Menge der

Algorithmen ab, zähle die Menge der Funktionen ab. Erinnern Sie sich noch, wie das ging? Vergleiche, also es gibt nicht Berechenbare Funktionen. Das war die Aussage in die Grundlagen der Programmierung 1. Und wir haben ja das bewiesen. Wir haben die Funktionen gezählt und wir haben die Algorithmen gezählt und haben gesehen,

Mensch, es gibt ja wahnsinnig viel mehr Funktionen als Algorithmen. Da muss es ja darunter Funktionen geben, die nicht durch Algorithmen darstellbar sind. Die Menge der Funktionen ist nämlich überzählbar. Die Menge der Algorithmen ist abzählbar. Also gibt es mehr Funktionen als Algorithmen. Also gibt es nicht berechenbare Funktionen. Das war die simple Beweistechnik in Grundlagen der Programmierung 1. Und hier taucht dieses Zählen der Algorithmen ab.

Da haben wir die Algorithmen abgezählt. Ersetzen Sie mal Algorithmus durch Programmen, dann würden Sie die Programme abzählen. Und dann ist die Frage, wo fangen Sie an zu zählen? Denken Sie sich jetzt die Java-Programme. Wo ist mein erstes Java-Programm? Abzählen heißt ja jetzt, Sie können den

Java-Programmen, Nummern zuordnen. Und dann können Sie sich auf irgendeine Reihenfolge festlegen. Wie ordne ich jetzt den Java-Programmen, welche Nummern zu? Und dann gibt es auch eins, das sich Nummer 1 kriegt. Was ist mein erstes Java-Programm? Und wir fragen, was ist das eine Millionste Java-Programm?

Nach irgendeinem System. Wie lautet das Computer-Programm? So und da jetzt schreibe ich das hier in lexikografischer Reihenfolge. Wir wollen ja also in irgendeiner Weise anordnen, die Computer-Programme. Wir fangen mit dem Kürzesten an. Das allererste, kleinste, kürzeste Java-Programm gewissermaßen. Wir nehmen nicht Java, sondern eine andere Programmiersprache. Was ist unser allererstes Computer-Programm?

Was ist unser zweites und drittes? Und was ist unser millionstes? Und die ordnen wir in so einer lexikografischen Reihenfolge an. Also wie so ein Lexikon in der Reihenfolge. So können Sie jetzt praktisch im Lexikon aufschlagen. Und das allererste Programm vorne, das steht da. Und dann blättern Sie weiter und gucken, wie

lautet denn mein ein millionstes? So und der traditionelle Zugang wäre jetzt so, wenn wir es lexikografisch machen, dann würden wir ja folgendes machen. Wir könnten ganz primitiv einfach alle Zeichenfolgen erzeugen. Erstmal die Zeichenfolgen mit einem Buchstaben A, B bis Z. Da ist

kein Programm drunter. Oder gibt es ein Programm, ein Java-Programm mit nur einem Buchstaben? Glaub nicht. Muss immer mit, mit, wie heißt das, womit fängen die immer an? Include sowieso irgendwas. Gibt es eins mit zwei Buchstaben? Gibt es wahrscheinlich auch nicht. Mit sowieso B, Z, Z, Z. Zwei Buchstabige gibt es nicht.

Dann machen wir mit drei. Irgendwann kriegen wir eins. Ich nehme jetzt mal an, hier, das wäre so ein Pascal-Programm oder was. Irgendwann fängt eins an mit Programmend. Da, da ist unser allererstes Programm, unser allererstes Pascal-Programm in lexikografischer Reihenfolge. Das würden wir jetzt in unser Buch übernehmen. So, dann geht das weiter, geht das weiter, ja. Und irgendwann kommt das millionste. Und wenn man das

jetzt systematisch machen würde, dann würde man ja, weil man nicht die Programme sozusagen nicht der Reihe nach erzeugen kann, sondern wir würden gewissermaßen alle Texte der Reihe nach erzeugen, immer wieder in den Compiler reinstecken. Und wenn er irgendwann mal sagt, oh, das ist ein korrektes Pascal-Programm, ein korrektes

Programm, dann würden wir sagen, das ist unsere Nummer sowieso, Nummer i. Und dann kommen wieder eine ganze Menge Zeichenfolgen, noch mehr Zeichenfolgen. Plötzlich kriege ich mal wieder ein Programm darunter. Das wäre dann unsere Nummer i plus eins. Ja, so wäre es. Also fütter den Compiler mit allen Zeichenfolgen, fängst von A an und machst die Zeichenfolgen immer länger, ja. Einfach immer, ich würde sagen, immer den

lexikografischen Nachverver. So, und dann gib die syntaktisch korrekten Zeichenfolgen aus und gib den dann passend der Reihe nach die Nummer. Das kann man machen, wenn man viel Zeit hat oder einen wahnsinnig schnellen Rechner, kann man so was machen. Aber in der Regel kriegt man da keine Programme raus, weil das ewig dauert, bis man das erste kriegt schon. Ja, hier das erste ist ja schon hier mindestens 20

Zeichen lang. Das heißt, sie haben also 26 hoch 20 Schleifendurchläufe schon gehabt, ja, wo sie immer wieder die Buchstaben erhöht haben, bis sie dieses hier rausgekriegt haben. So, und das Millionstitel kommt dann noch viel, viel später, ja, weil alle Millionen Male kommt man

mal wieder ein Programm raus. Das erste, das nächste, was hier käme, wäre vielleicht hier, wo sie beim ersten Mal, was wäre das so? 1 gleich 1 oder so, wäre ja als Rumpf oder x gleich 1 oder eben so was, x gleich x, irgendwie a gleich a

wahrscheinlich, ne? Irgendwie so ein Programm wäre das nächste, ja, und das dauert aber schon wieder ewig lange, bis sie das machen können. So, und da wäre die Idee, ist jetzt folgende, wir erzeugen gleich die syntaktisch korrekten Programme und dann nehmen wir jetzt keine Programmiersprache dazu, sondern so eine spezielle neue Programmiersprache, in der man das relativ gut machen kann, wo man dann auch die Variablen

vernünftig erzeugen kann und die Variablen irgendwie vernünftig durchnummerieren kann. Also die vereinfachte neue Programmiersprache, die sieht jetzt so aus, die kann nur machen, x i ergibt sich aus 0, x i ergibt sich aus x j plus 1 und while x i ungleich x j du und ot.

Das ist das 1, 4. Und Schleifenrumpfe sollen nicht leer sein. Und als Variablen gibt es nur x 1, x 2 und so weiter mit angeschlossenen natürlichen Zahlen, die dann auch beliebig groß werden können. Ja, also das sind eigentlich unsere einzigen Variablen und Ein- und Ausgabe sind dann die Anfangs- und Endwerte endlich vieler Variablen.

Fertig, mehr passiert nicht. So, und diese diese Sprache, die hat auch in der Literatur meistens eine Bedeutung, wo es nur wild Schleifen gibt. Ja, das ist die sogenannte Sprache der wild Schleifen, weil wild Programme und man fragt sich manchmal, was kann man mit wild Schleifen machen? Sie haben hier zum Beispiel kein if-then-else drin. Fällt Ihnen das auf? Brauchen wir das oder fehlt uns da was?

Das haben wir, if-then-else haben wir nicht. Also in wild Programmen gibt es kein if-then-else. Die Frage ist, kann man damit leben? Kann man, kann man simulieren? Ja, ist auch so, kann man tatsächlich simulieren. Auch if-then-else und so kann man, kann man durch wild simulieren. Sie müssen halt nur dafür sorgen, dass beim wild eben nur ein einziger Durchlauf stattfindet. Da haben Sie ja if-then, wer nicht?

Also so solche Sachen kann man simulieren. Deswegen kann man sie dann auch weglassen. Und also das ist die Sprache der wild Programme. So und hier habe ich mal ein Programme hingeschrieben. Also so Zuweisungen hier zum Beispiel können Sie realisieren. Die haben wir ja auch nicht. Wir haben nur x, j ergibt sie aus 0. Ja und sowieso plus 1. Aber eine Zuweisung kann man realisieren, ist hier so ein kleines wild Programme.

Subtragieren ist ein bisschen schwieriger. x, j ergibt sie aus 0, xk ergibt sie aus 0 und dann wild. Also irgendwas zu subtragieren heißt, Sie müssen den kleineren, den um 1 kleineren ermitteln und dem, dem neuen zuweisen. Subtragieren können Sie nämlich sonst auch nicht, haben Sie keine Operation dazu. Also in x, j machen wir x, i minus 1

rein und das geht nur, indem wir feststellen, hier in dem x, k, wie groß denn x, i minus 1 ist. Und da lassen wir x, k von 0 laufen bis zum Wert x, i und ergänzen sozusagen den entsprechenden Wert

hier in das x, j rein. Da soll er ja hin. Passiert das hier also, ne? So und wenn wir dann x, i erreicht haben, dann haben wir hier in x, j gerade x, k gespeichert und x, k war gerade x, i minus 1. Solche Operationen kann man also durchführen. Also ein bisschen was kann man machen mit so einer Sprache, die selbst

so primitiv ist und da entsprechend dann so Programme bilden. Gut, wir sind am Ende angekommen. Ich zeige da beim nächsten Mal, was wir noch ein bisschen an Voraussetzungen dazu brauchen, damit wir solche Programme systematisch auch der Reihe nach erzeugen können, syntaktisch. Gut, bis nächste Woche.

Gut, ja, willkommen zur Vorlesung. Wir sind dabei, mit unserer WALP-Programm, Programmiersprache

der Reihe nach Programme zu erzeugen. Und da waren wir bei diesem Beispiel beim letzten Mal stehen geblieben und kümmern uns jetzt darum, wie solche Programme, die wie die Programmiersprache gestaltet werden, kann, damit wir der Reihe nach tatsächlich auch Programme erzeugen können und nicht das zwischendurch, wenn man normalerweise eben Texte erzeugt, dann sind

die meisten Texte ja keine Programme. Und infolgedessen muss man jedes jeden einzelnen Text immer daraufhin überprüfen, ob er korrektes Programme ist und nur dann die korrekten Programme auch tatsächlich zählen. Und wir erzeugen jetzt mit einem mit einem besonderen Mechanismus tatsächlich Programm auf Programm. Ja, und dazwischen sind keine Leichen, die nicht als Programme gelten. Und dazu verwenden wir

noch so ein Variablen Ordnungsprinzip. Wir haben ja prinzipiell die Möglichkeit, Variablen zu bilden in der Form X, J ja und hier hinter ist einfach ein beliebiges, eine beliebige Zahl und wir nummerieren also die Variablen einfach durch und wir vereinbaren jetzt das Variable X, I in einem Programm erst dann

verwendet werden kann, wenn alle X, J vorher schon verwendet wurden. Ja, dadurch kriegen wir so eine gewisse Bündelung der Programme oder eine gewisse Reihung der Programme, beginnend bei denen, die wenige Variablen verwenden. Das sind dann, sagen wir mal, nur die Variablen X, I bis X, I. Ja, und man kann nicht einfach Programme erzeugen mit X, I, X, I plus 1 oder irgendwelchen höheren

Zahlen, wenn man nicht vorher alle anderen Variablen schon verwendet hat. Sonst funktioniert das nicht. So, und sonst gäbe es eben eine unzählige, unendliche Zahl von Programmen. Zum Beispiel X, I ergibt es ja aus 0, X, II ergibt es ja aus 0, X, III ergibt es ja aus 0. Jedes als einzelnes Programm betrachtet. Ja, und jedes Mal wäre es eigentlich dasselbe Programm mit derselben Funktion.

Und wir könnten unendlich solche unendlich viele solche Programme erstellen. So, und das wollen wir wollen wir vermeiden, indem wir die Variablen eben der Reihe nach nur einsetzen dürfen. Also erst die, also wir beginnen bei 1, 2, 3, also beginnen bei den kleinen Zahlen I und dann erst zu höheren Zahlen übergehen können, wenn wir alle vorherigen

Variablen schon mal mindestens einmal benutzt haben. So, und wenn das ist, dann kann man diese, diese fünf Programme, die ersten fünf Programme nämlich tatsächlich angeben. Also das allererste Programm kann natürlich nur mit einer Variable arbeiten, die X, I heißt. Und das einzige Programm, das kürzeste und auch lexikografisch allererste Programm ist eben

dieses hier. X, I ergibt sie aus 0. So, und das zweite Programm, was macht das? Das kann dieselbe die dieselbe Variable verwenden. X, I ergibt sie aus 0 und X, I ergibt sie aus 0. Mehr geht nicht. Das ist das kürzeste Programm, was danach kommt. Aber es gibt noch ein zweites Programm hier dieser Art,

nämlich das, wo hier die zweite Variable verwendet wird. Und die dritte Variable, X, I darf nicht verwendet werden. Ja, hier also im Austausch dazu, weil ich dann X, II nicht verwendet hatte. Und ich darf auch nicht bei X, II anfangen, weil ich X, I dann nicht verwendet habe. So, und jetzt können Sie sehen, das ist tatsächlich auch eine lexikografische Reihenfalle.

Denken Sie sich daran, die Dinge würden jetzt also alphabetisch angeordnet, lexikografisch. Dann ist dieses eben ein späteres Programm. Und jetzt können wir das nächste Programm angeben. Jetzt kann ich hier quasi ein Programm nehmen, das ist lexikografisch hinter diesem hier. X, I ergibt sie aus X, I plus 1. Und jetzt gucken Sie wieder, was

kann man machen stattdessen? Wir können auch machen X, I ergibt sie aus X, II plus 1. Hier darf ich sozusagen die Variable erhöhen. So, und da haben wir die ersten fünf Programme in dieser lexikografischen Reihenfolge. Und damit sind die ersten Programme, und zwar alle Programme mit maximal zwei

variablen Referenzen, sind damit schon aufgezählt. So, das ist der erste Trick, also die Numerierung der Variablen geschickt zu gestalten. Und der nächste Trick ist, mit sogenannten Templates zu arbeiten. So, was sind Templates? Schauen Sie sich mal hier dieses Programm an. X, I ergibt sie aus Null.

Und dann weil sowieso X, I, X, I ist 1. Hier haben wir jetzt also im Prinzip ein Template, wo wir nur noch unter der Nebenbedingung der Reihenfolge der Variablen hier andere Variablen einsetzen könnten, aber im Prinzip immer dasselbe Programm behalten. Also dieses Ding ist quasi ein Template und

das ein anderes Programm. Dieses selben Templates wäre zum Beispiel dieses hier. Und hier sehen Sie wiederum, hier haben wir also die Variablen-Anordnung haben wir eingehalten. 1, 2, 3, 4. Und dann 5 darf hier unten erst verwendet werden und ist auch richtig verwendet, weil ich alle vorherigen Variablen vorher schon einmal verwendet habe. Also beide Programme und

unterscheiden sich jetzt eigentlich nur in der Verwendung der Variablen. Ansonsten ist eigentlich alles identisch zwischen diesen beiden Programmen. Und jetzt wäre es doch mal eine gute Idee, sozusagen diese beiden Programme einfach als Ausprägungen ein und dasselben Templates zu betrachten. Und das Template sieht dann so aus.

Wir lassen die variablen Nummern weg. X gibt es ja aus 0, weil X ungleich X, X und so weiter überall die Nummern weggelassen. Dann bleibt dieses Template über. So, also Templates sind im Wesentlichen syntaktisch korrekte Programme, wenn man die Variablen entsprechend der vorgegebenen

Regel zur Variablennummerierung mit Nummern versieht. Und dann kriegt man ja wieder dieses Programm hier oder jenes Programm. So, und das, das kann man jetzt geschickt machen. Man kann jetzt erst mal versuchen, die Templates zu erzeugen. Und innerhalb der Templates dann die Variablen entsprechend dieser Regel sozusagen der Reihe nach

durchzunummerieren und hoch zu zählen. Dann würde man also anfangen. Wenn dieses Template kommt, dann entstehen aus diesem Template, sagen wir mal, wie viele sind das? Kann ich jetzt nur gar nicht sagen. Ich sag mal 100 weitere Programme. Und jedes dieser Programme ist entstanden durch Untereinhaltung der Variablennummerierung eine

Nummernzuordnung dieser entsprechenden Template Variable. Also 1, 1, 1, 1, 1. 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1. So und so weiter. So würden Sie jetzt praktisch aus diesem Template hochzählen können. Und das Höchste, was Sie

kriegen können, ist eben 1, 2, 3, 4, 5, 6, 7, 8. Also bis zur Variable Nummer 8 können Sie jetzt hochzählen, die einzelnen Variablen über diese Templates. So, also ein Template ist so ein taktisch korrektes Programm, bei dem man jedes Variablen vorkommen x i durch x ersetzt. Das sind also diese

Templates. Dann ersetzen wir also diese entsprechenden Nummerierungen und lassen die weg. Und die Strategie, jetzt die Programme aufzuzählen und dann irgendwann das Millionstil zu bekommen, ist, wir zählen die Reihe nach die Templates auf. Dann kriegen wir immer längere Templates. Und von Template zu Template

ergänzen wir die entsprechenden Programme durch passende Nummerierungen der nach dem Ordnungsprinzip zulässigen Variablen zu ordnen. So, und dann kriegt man die Templates werden natürlich entsprechend länger. Die haben dann viel mehr Variablen auftreten. Sagen wir mal 100 verschiedene Variablen.

Und jetzt zählen sie sozusagen die Variablen Nummern entsprechend durch und dann kriegen sie für dieses Template an der Position, sagen wir mal 500.000. Nochmal die nächsten 100.000, die nächsten 500 Stellen abgedeckt durch die entsprechenden Variablen Nummerierungen. Und dann kommt das nächste Template, was länger ist.

Und mit den entsprechenden Variablen Nummerierungen kriegen sie dann wieder das neue Million, also die neue Kette von neuen Programmen dazu. So, und jetzt müssen wir im Prinzip Folgendes gucken, wie zählt man Templates auf? Und dann müssen wir gucken, was ist das letzte Template vor der eine Million? Und dann muss man gucken,

wie viele Variablen Zuordnungen gibt es, damit ich sehen kann, welche dieser Variablen Zuordnungen auf das letzte Template vor der eine Million ich brauche, damit ich an der Position eine Million komme. So, und da ist auch wieder ein bisschen Know-how dabei und ein kleines bisschen Mathematik. Da kommt dann so eine neue,

diese vielleicht ja auch so Mathematik. Sie machen ja Mathematik, kennen Sie vielleicht eine entsprechende Zahlenfolge raus, ein bestimmtes Rechenschema dazu. So wie diese diese Zahlenpyramide, ja, die kennen Sie vielleicht. Also zunächst erst mal nach der Aufzählung der Templates. Also wenn wir so Templates

aufzählen, dann ist unser allererstes Template x ergibt sich aus 0. Das nächste Template x ergibt sich aus 0, x ergibt sich aus 0. Das sind diese Reihenfolge, kennen Sie schon aus der Aufzählung der ersten fünf Programme. Das nächste war x ergibt sich aus x plus 1 und dann x ergibt sich aus 0, x ergibt sich aus 0,

x ergibt sich aus 0. Template Nummer 1 bis 4. So müssen wir die also aufzählen. So, dann geht's weiter mit Template Nummer 5. Da kommt zum ersten Mal die Rechnung rein. Template Nummer 6, Template Nummer 7. Da ist das erste Wahlprogramm und so weiter. So entsprechend haben wir diese Templates.

So, und diese Templates, die sind jetzt angeordnet nach der, nach dem Anzahl der Auftreten der Referenzen. Hier haben wir also die eine Referenz. Zwei, zwei, drei, drei, drei, drei. Ja, also wir sind irgendwie in den, bei den Templates mit den entsprechenden Dreierreferenzen.

Also so sieht das aus. Lexikografische Reihenfolge bilden, x ergibt sich aus 0, x ergibt sich aus x plus 1. So, und die die entsprechende Reihenfolge hier mit der entsprechenden Reihenfolge erhöht sich die Zahl der Referenzen hier auf die entsprechenden Variablen. So, und jetzt kann man diese Zahl der Referenzen, ja, jetzt können Sie

können Sie praktisch hochzählen über diese Templates und dann können Sie wenigstens schon mal sagen, wie das millionste Template aussieht. Das millionste Template hat 16 Variablenreferenzen. Hier ist es. So, x ergibt sich aus 0, x ergibt sich aus 1, 2, ja, so und so viel können Sie alle durchzählen. Das ist das millionste Template.

So sieht das aus. So, und Sie sehen das, eine Million erste, das würde jetzt an dieser Stelle hier hochzählen. Hier würden Sie x ergibt sich aus x plus 1 haben als nächstes Template. Und dann zählt das hier sozusagen sukzessive hoch. Sie müssen das so mehr oder weniger wie so ein Stellenwertsystem betrachten,

das nur ein bisschen komisch aussieht. So, und jetzt haben wir so ein Template. Und jetzt ist die Frage, wie viele Variablenzuordnungen gibt es denn jetzt unter Berücksichtigung dieses Ordnungsprinzips? Also erst die Variablen mit der Nummer 1 verwenden. Und wenn ich eine Mal eine 1 verwendet habe, dann die Zweier, die Dreier und so weiter.

Also auf wie viele verschiedenen Weisen kann ich jetzt unter Berücksichtigung des Ordnungsprinzips diesen 16 Variablenreferenzen hier oder überhaupt eben bei solchen Programmen die entsprechenden Zuordnungen vornehmen. Also 1, 1, 1, 1, 1 an allen Stellen. 1, 1, 1, 1, 1 bis zu dieser Stelle hier eine 2.

1, 1, 1, 1, 1 bis zu dieser Stelle hier eine 2, hier eine 1 und so weiter. Und wie viele verschiedene Möglichkeiten gibt es da? So, und diese Zahl der Variablenzuordnungen, die verhält sich nach den sogenannten Bellzahlen. Haben Sie da mal von gehört? Irgendwie? Bellen an was? Nie irgendwie gehört so.

Mathematik. Irgendwie was Simples. Also in der Schule macht man es normal nicht. Da kennt man nur dieses Pythagorelische 3. So was. Und die Bellzahlen sind so von einer Anordnung sehr ähnlich. Also wie entstehen die? Wir geben seine Menge M mit N Elementen

und die Bellzahl B von N ist die Anzahl der Partitionen von M. So oder? Partitionen, die Aufteilung der Menge in unterschiedliche Teilmengen, sodass die die Zusammenbündelung die die entsprechenden Mengen ergibt. So, also wenn Sie die Menge bestehen haben, nur aus dem einen Element,

dann gibt es nur die Partitionen, die genau aus diesem einen Element steht. Also die Bellzahl ist 1. Wenn Sie die Menge A B haben, dann können Sie sagen, entweder habe ich nur die Menge A B, das ist die eine Partition, oder ich teile sie auf in zwei Mengen A und B. Das ist die andere Partition. Also Bellnummer 2. Und wenn Sie A B C haben,

dann können Sie sagen, ich habe die ganze Menge A B C oder ich teile neben A C und B oder ich nehme A und B C oder ich nehme A B und C. Das ist immer 2 mit 1 zusammen. Gibt nochmal 3 Partitionen oder ich teile eben hier auf in A B und C. Also für eine Menge der Größe 3 ist die Bellzahl 5.

Die Anzahl der Partitionen, die Sie bilden können, aus dieser Menge. So und diese Bellzahlen, die entsprechen jetzt genau diesen variablen Positionen. Wenn Sie jetzt ein Programm Template mit N variablen Positionen haben, M1, M2 bis MN.

Eben hatten wir 16 variablen Positionen bei dem millionsten Template. Dann kann jede Partition P1, P2 bis PK von dieser Menge als Zuordnung der Variablen XI an die Position PI verstanden werden. So also K variablen Positionen,

N variablen Positionen. Und wenn ich jetzt die entsprechenden Variablen X1 bis XN ja diesen Positionen zuordne, dann kann ich da eine entsprechende Partition, das entsprechende als Partition verstehen. Jetzt schauen wir mal hier ist so ein Template.

So und was kann ich maximal vergeben? 1, 2, 3, 4, 5, 6, 7, 8. Also acht verschiedene variablen Indizes kann ich hier vergeben. So und jetzt ist die eine Partition ist, ich nehme diese acht. Das wäre die Partition, wo ich die Menge gar nicht teile, sondern die gesamte Menge als Partition betrachte.

Dann ordne ich hier 1, 2, 3 bis 8 zu. So eine andere Partition ist 1 und dann 2, 3 bis 8. Dann nehme ich eben 2, 3 bis 8 nicht, sondern nehme an alle Positionen die 1. Also oder ich habe eine Partition wie diese hier 1, 2 und dann 3, 6, 7,

dann 4 und dann 5, 8. Das bedeutet jetzt eben hier die Positionen 1 und 2 kriegen die Variable Nummer 1. Die Positionen 3, 6 und 7 kriegen die Variable Nummer 2. Die Position 4

kriegt die Variable Nummer 3 und die Positionen 5 und 8 kriegen die Variable Nummer 4. So und die kann ich jetzt hier praktisch an die entsprechenden Positionen anordnen. Dann 3, 2, 6, 7 und die anderen eben auch. x3 gleich 0, x4 gleich x2 plus 1

und x2 gleich x4 plus 1. Und wir sehen, wir haben das Ordnungsprinzip eingehalten. Ja, keine Variable wird verwendet, bevor nicht eine frühere verwendet worden ist. So und alle diese Partitionen, die jetzt möglich sind, entsprechen solchen Zuordnungen hier. Und hier haben wir jetzt 8. Das heißt, die Bellzahl von 8 würde jetzt festlegen,

wie viele verschiedene Zuordnungen von variablen Bezeichnern, von variablen Nummern ich für dieses Template vergeben kann. So und wenn wir jetzt dieses Millionstetemplate angucken, ja, dann würde also die Bellzahl 16 würde jetzt sagen, wie viele verschiedene Programmchen ich mit diesem Template bilden kann. Die kommen dann auf die Million drauf.

Und wenn diese ganzen Templates alle abgearbeitet sind, dann kommt das eine Million erste Template mit seiner entsprechenden Zahl von verschiedenen Programmen. So, jetzt gucken wir die Bellzahlen nochmal an. Die Bellzahlen, die die lassen sich eben so rekursiv bilden hier. Also b n plus eins ist die Summe aller Bellzahlen

von k gleich 0 bis n mal n über k. Und b 0 ist 0. So, wie berechnet sich das? Zähligt man eine n elementige Menge in das Jungte Teilmengen mit jeweils k und n minus k Elementen, so gibt es n über k Möglichkeiten. Man fügt nun das n plus

erste Element zu jeder dieser n über k Möglichkeiten hinzu. Und da die die Bellzahl b k, die Anzahl der Partitionen von einer k elementigen Teilmenge ist, liefert die Summation über die verschiedenen Möglichkeiten, die man da kriegt, liefert eben die entsprechende Bellzahl n plus eins.

So, und das Ganze geht dann über so ein Belldreieck, so wie das paschalsche Dreieck, das fiel mir der Name nicht ein, also so wie übers paschalsche Dreieck. Da fängt man also an, hier irgendwie über so eine entsprechende Anordnung da Summen zu bilden. Wir müssen ja immer Summen über diese n über k mit den entsprechenden Bellzahlen bilden.

Also eins plus eins. Und dann bildet sich daraus dann hier so über dieses Dreieck dann die entsprechende zwei. Und jetzt geht es dann hier unten weiter. Da unten kommt jetzt die neue Bellzahl hin. So, und dann wird wieder über die entsprechenden hier weiter addiert. Da haben wir dann hier die Bellzahlnummer,

die Bellzahl von zwei ist drei. So, und zwei plus drei, die entsprechende Bellzahl wird dahingebildet. So, und dann rutscht die da unten hin hier zur fünf. So, und addiert man hier wieder. Dann kommt hier die sieben raus. So, und dann hier entsprechend die zehn.

So, und dann die die 15. So, und jetzt rutscht diese 15 da unten wieder hin. So entsprechend kommen diese Werte raus hier. 20, 37, 52. So irgendwie bildet sich das. Pardon, so bildet sich das Belldreieck noch mal schnell.

So, und da die fünf, zack, zehn. So, und da oben.

15, da, so da gehen, hier oben liest man die also ab. So, und da kam die nächste hier und dann da die oben die nächste. So, Bellzahl 203. Ja, ja, so sieht's ja aus.

So, und jetzt haben wir hier haben wir gerade die die entsprechende Variabel an Referenzen acht hier. So, und jetzt haben sie nicht mitgerechnet. Ich eben auch nicht. Aber mein schlaues Skript sagt, also bei acht Variablen Referenzen gibt es 4140 Möglichkeiten

der Variablen Belegung. So, und dieses Template hier, das würde jetzt quasi das ist, sagen wir mal, an der Position K. Und dann kommen noch K. Also K und dann bis K plus 4139. Das sind die entsprechenden Programme, die jetzt entstehen, sozusagen. Und dieses dieses ganze Cluster,

dieser Block gewissermaßen, der wird dann abgelöst durch das nächste Template. Und dann haben wir für das nächste Template. Vielleicht haben wir da wieder acht Variablen Referenzen. Ja, die erhöhen sich ja nicht unbedingt, sondern es kann sein, dass einfach nur irgendwie das While neu hinzukommt oder so. Und dann durch ein X, das ergibt ja das X plus eins, irgendwie gegen While ausgetauscht wird.

Also dann kommen jedenfalls noch mal wieder die entsprechenden nächsten dazu. So, und jetzt kann man gucken. Das erste Programm mit zehn Variablen Referenzen kann man jetzt wirklich ausrechnen. Wo ist das wirklich? Das ist die Nummer 19 Millionen. Da ist das erste Programm mit zehn Variablen Referenzen. So und das letzte mit zehn Variablen Referenzen

bei 272 Millionen. So, also so viele. Wir haben hier grob irgendwie 250, 252, 253 Millionen verschiedene Programme gibt es mit zehn Variablen Referenzen. Schon ein ganz schöner Hammer. So, und das ist jetzt natürlich immer.

Da sind eben viele Templates dabei, jeweils und jedes hat zehn, zehn Variablen Referenzen und die Bellzahl von zehn ist jetzt nicht so riesig groß. Ja, aber die vielen Templates, die alle zehn Variablen Referenzen haben, die sorgen im Prinzip dann für die entsprechende Multiplikation auf diese vielen 250 Millionen da.

So, das Millionste Programm, das kann man jetzt wirklich angeben. Und das der Auto, der das gemacht hat, der hat das also tatsächlich hier so ausgerechnet. Ja, das ist das millionste Computer Programm, weil x1 und gleich x2, du x3, da gibt es ja null. Ja, nicht viele Variablen x4, da gibt es jetzt 1 plus 1, x5, x6, ja.

Eben waren wir ja bei dem Template schon bei 19 Millionen. So, und wir müssen auch viel früher anfangen. So, das ist das millionste Computer Programm. So, und das Überraschende ist eigentlich irgendwie, das ist ja ziemlich, ziemlich kurz. Man hätte jetzt, ich weiß nicht, ob Sie jetzt mehr erwartet hätten. Ziemlich, ziemlich kleines Programm eigentlich.

Und wenn man da in reale Programmiersprachen reinguckt, da sind die Programme noch viel kürzer. Also wenn Sie jetzt das millionste Java Programm nehmen, das ist noch viel kürzer, weil Sie viel mehr Möglichkeiten haben irgendwie und die Variablen vergrößern können um alles mögliche. Ja, also diese

Benennung der Variablen, die sorgt dafür, dass das wirklich überhaupt mal ein Programm entsteht an der millionsten Stelle. Was noch irgendwie ein vernünftiger, wie dieses hier eben eine vernünftige Optik hat, wo man wirklich sagen kann, das sieht irgendwie noch was aus. Da wird anscheinend irgendwas gerechnet. Ja, und nicht nur 0, 0, 0, 0, 0, 0, da gibt es ja auch 0, 0, 0, 0 und so weiter. So also in realen Programmiersprachen

sind diese noch viel kürzer. Und wenn man jetzt guckt, wie weit man kommt dabei insgesamt, ja, wenn man hat 50 Millionen Templates gibt es mit 20 Variablen, 50 Millionen Templates mit 20 Variablen. So und jetzt müssen wir die Bellnummer von 20 gucken. Da ist sie ja.

Ach so, die ist dann groß. Da geht das Ding irgendwann ab. Das ist so wie die Fibonacci-Zahlen auch. Das dauert ziemlich lange, aber die wachsen halt exponentiell. So und hier ist es eben auch die Bellzahl von 20 ist größer 50 Milliarden. Und dann haben sie für jedes dieser 50 Millionen Templates eben diese 50 Milliarden

verschiedenen Variablenbelegungen dazu. So und das sind jetzt, die können Sie multiplizieren. Man hat 2,5 mal 10 hoch 18 Programme mit 20 Variablen. So und 20 Variablen ist nix. Miniprogrammchen. Ja, dann kann man gerade Primzahlen mitrechnen. Brauchen wir ein bisschen weniger.

Irgendwie viel mehr kann man nicht machen mit 20 Variablen. Aber da gibt es schon wahnsinnig viele Programme. Das ist das Überraschende dazu. Mehr als Atome im Weltall mit 20 Variablen. Glaube ich wenigstens. Das ist das Mehr, mehr Atome.

Gut, das ist überraschend. Vielleicht gut, also das das wollte ich Ihnen zeigen. Ja, also was? Was ist das Besondere jetzt an diesen ganzen Verfahren? Ja, man zählt ab, man zählt auf. Wir wissen jetzt, was Abzählbarkeit und Aufzählbarkeit ist. Wie immer und ewig. Was der Unterschied ist. Wir zählen hier Programme ab und wir haben ein richtiges Verfahren und Programme auch mal

tatsächlich wirklich durchzuzählen und auch wirklich so systematisch zu erzeugen. Und dazu haben wir extra eine Programmiersprache definiert und ein bestimmtes Verfahren, mit dem das dann auch vernünftig funktioniert. Damit man die auch wirklich sauber durchzählen kann. Gut. Das wollte ich Ihnen zum millionsten Computer

Programm erzählen.