EIG044 LODA (mit Christian)

0:17Thomas Kahle Hallo zusammen, ich begrüße alle zu einer neuen Folge Eigenraum und heute, man erkennt es schon an dem grünlichen Cover, habe ich mal wieder einen Gast eingeladen und mein Gast heute ist Christian Krause. Hallo Christian, freue mich sehr, dass du da bist.

0:34Christian Krause Hallo Thomas, danke für die Einladung.

0:36Thomas Kahle Ja, also was verbindet uns? Also ich würde sagen, was uns verbindet, ist vielleicht ein gemeinsames Interesse oder fast schon eine Zuneigung zur OEIS, der Online-Enzyklopädie der Integer Sequences, die ja hier im Podcast eine regelmäßige Rolle spielt und ich würde mich als Fan bezeichnen. Würdest du dich auch als Fan bezeichnen?

0:55Christian Krause Als Fan nicht. Ich finde es auf jeden Fall interessant. Ich bin da vor einiger Zeit drauf gestoßen. Ich finde, es ist ein Phänomen auf jeden Fall. Und man findet da interessante und spannende Sachen und hat auch viele Verbindungen letztendlich zu Informatik. Und deswegen habe ich da im Prinzip auch vor einigen Jahren ein Projekt gestartet, Loda, was in dem Bereich im Prinzip auch angesiedelt ist.

1:16Thomas Kahle Genau, also du bist vielleicht zum Background ein bisschen, du bist Informatiker von der Ausbildung her oder auch Mathematik interessiert. Wie würdest du das beschreiben?

1:24Christian Krause Genau, ich bin Informatiker, war relativ lange auch in der Forschung unterwegs, bin dann aber irgendwann abgebogen in die Wirtschaft, weil es halt doch irgendwie bessere, attraktivere Arbeitsbedingungen geboten hat. Genau, Mathe war schon immer eigentlich auch mit als Interesse auf jeden Fall dabei. Matheaffin, vor allem natürlich so Sachen, ich meine, wenn es jetzt um OIS geht, so Bereiche wie Sozialentheorie, das ist was, glaube ich, viele, die Matheaffin sind, auch spannend finden.

1:49Christian Krause Genau, ich hatte dann am Anfang beim Studium auch überlegt, im Prinzip Mathe als Nebenfach zu machen, habe es dann nicht gemacht, war aber dann aber auch nicht unzufrieden, weil besonders am Anfang bei mir im Studium ich sehr gute theoretische Informatik-Vorlesungen hatte und mich da eigentlich sehr wohl gefühlt habe.

2:06Christian Krause Trotzdem ist das immer noch so ein Hobby geblieben, also speziell jetzt so der Bereich Zahlentheorie, auch die Verbindung letztendlich zu... Ich sage mal, Antbereiche zur Informatik, Berechenbarkeitstheorie, Rekursionstheorie und solche Geschichten, das fand ich eigentlich immer spannend. Auch im Mathekontext selbst, die Verbindung von der Zahlentheorie in andere Bereiche von der Mathematik, zum Beispiel analytische, algebraische Methoden, das ist natürlich sehr spannend.

2:35Christian Krause Und da angesiedelt ist natürlich die UES als im Prinzip Datenbank für Zahlenfolgen.

2:42Thomas Kahle Ich komme ja so ein bisschen aus der anderen Richtung, kommen wir uns so entgegen. Also ich bin ja jetzt in der Mathematik verwurzelt, aber genau immer dieser Blick auf die theoretische Informatik und auch Berechenbarkeit in der Mathematik, was kann berechnet werden, wie kann es effizient berechnet werden, ist ja hier auch im Podcast eigentlich relativ regelmäßig Thema und interessiert mich auch in der Forschung.

3:05Thomas Kahle Ja, hast du eine Lieblingsfolge in der OIS oder kann man es so nicht sagen?

3:09Christian Krause Nee, das kann man so nicht sagen. Ich würde sagen, letztendlich, also das Interessante ist natürlich, dass man im Prinzip alles Mögliche an Zahlenfolgen in der OES findet. Auch obskure Sachen, die eigentlich nichts mit Mathe zu tun haben. Das Interessante finde ich eigentlich nicht die Zahlenfolgen selbst, sondern was dahinter steckt.

3:27Christian Krause Im Prinzip letztendlich die mathematischen Strukturen oder Probleme, die sich dahinter verbürgen und die Zahlenfolgen selbst sind mehr so eine Art, ich weiß nicht, so ein Zeugnis oder so ein Fingerprint oder wie auch immer von dem, was da eigentlich dahinter steckt. Und ja, das Spannende finde ich eigentlich ist auch Verbindung, wenn man halt eine Zahlenfolge da in der OES findet, dann findet man natürlich auch direkt Links zu anderen Folgen und zu anderen Problemen und besonders wenn da halt unerwartete Verbindungen halt da sind, dann ist es natürlich immer interessant.

3:59Christian Krause Aber um deine Frage zu beantworten, nee, ich habe jetzt keine spezielle oder Lieblingsfolge.

4:05Thomas Kahle Ja, man könnte ja sagen, dass die OES irgendwie so eine Art Datenschatz ist, das ist so ein bisschen wie die Forschungsdaten der Mathematik oder so Laborergebnisse, die könnte man so eigentlich auch als so ein Open Science Projekt betrachten. Also dass die, ja, wie so Laborergebnisse oder Messergebnisse der Mathematik da veröffentlicht werden und eben mit allen möglichen Querverbindungen.

4:29Thomas Kahle Und die Leute, wie zum Beispiel du, können die einfach nehmen und daran ihre eigenen Experimente oder ihre eigenen Auswertungen machen und irgendwie zu neuen Erkenntnissen kommen. Also man kann es auch in diesem Kontext von so Forschungsdatenmanagement sehen, was ja jetzt eigentlich eine große Rolle spielt heutzutage.

4:48Thomas Kahle Also wenn man so in die Naturwissenschaften guckt und da wird das immer heißeres Thema, dass man eben diese große Zahl an Forschungsdaten, womit die meistens eigentlich so Messwerte und irgendwelche nicht reproduzierbaren experimentellen Sachen meinen, dass die eine immer größere Rolle spielen oder also dass es einfach immer mehr Daten werden und eben so ein Management für diese Daten aufgezogen werden muss. Aber in der Mathematik haben wir ja.

5:11Thomas Kahle Irgendwie die Reproduzierbarkeit. Und da sind wir ja eigentlich auch schon ein bisschen so bei Loda. Vielleicht wollen wir mal so ein bisschen erstmal über Loda reden, also ist ja auch der Folgentitel. Also ich weiß, Loda steht für Lexicographical Order Descent Assembly, also irgendwie eine Assembler-artige Programmiersprache, sag ich mal.

5:31Thomas Kahle Also kannst du vielleicht mal so eine kleine Einführung geben, was Loda ist und ist es durch OES entstanden oder bist du da irgendwie unabhängig, war das so unabhängig aus deiner Forschungszeit noch oder?

5:41Christian Krause Es kam jetzt nicht aus der Forschungszeit. Es ist letztendlich, also ich bin in der Forschungszeit auch auf die OES gestoßen und hatte mich eigentlich interessiert letztendlich für formale Beschreibungen der Zahlenfolgen. Also das Ground Truth oder wie auch immer die in der OES sind ja eigentlich die Zahlen selbst. Also der Prozess ist ja so, dass man da im Prinzip so ein Sample hochladen kann und dann Beschreibung dazu.

6:02Christian Krause Aber das Spannende fand ich jetzt eigentlich eher ist die Funktion oder eine Beschreibung, eine formale Beschreibung der potenziell unendlichen Zahlenfolge, die dahinter steckt. Und das kann halt in verschiedenen Arten natürlich definiert werden. Das kann so Rekursionsgleichungen sein, das können aber auch andere Schemata oder andere Sprachen sein, wie auch immer.

6:23Christian Krause Und den spannenden Aspekt fand ich, sich diese Datenbank zu nehmen, die Zahlen, die Daten zu nehmen und versuchen, das im Prinzip da Formeln oder Programme zu generieren bzw. Da zu reverse-ingenieren. Das heißt, man nimmt sich nur die Zahlen selbst, die Zahlenfolgen selbst und versucht, ohne weiteres Wissen darüber, letztendlich algorithmisch oder mit Informatikmethoden im Prinzip, dort formale Beschreibung von diesen Zahlenfolgen zu finden.

6:55Thomas Kahle Es ist ja eigentlich so dieses typische Anwendungsfall, würde ich sagen, den man jetzt aus der Mathematikforschung hat für die OIS. Man hat irgendwie ein mathematisches Objekt oder eine Familie von Objekten, die man untersucht und dann zählt man irgendwas nach und für Parameter n gleich 1 kriegt man eine Zahl raus, für n gleich 2 kriegt man eine Zahl raus, für n gleich 3 kriegt man eine Zahl raus und hat dann irgendwie nur so ein paar Datenpunkte und findet dann mittels OIS zum Beispiel eine Formel oder eben Verbindungen, also die Zahlen, die man jetzt beobachtet hat, das sind die Zahlen.

7:24Thomas Kahle Sind auch diese und diese Zahlen, die in irgendwelchen anderen Kontexten aufgetreten sind.

7:30Christian Krause Genau. Das Spannende ist natürlich, wenn diese Zahlenfolge in der OES ist oder eine nahe Verwandte, dann findet man die natürlich. Aber wenn es halt eine ist, die vorher noch nicht existierte, dann ist es natürlich interessant, dort algorithmisch im Prinzip was zu generieren dafür. Aber letztendlich ist eigentlich das Ziel, sich den Datensatz zu nehmen und im Prinzip für das, was schon in der Datenbank steht, schon im Prinzip Programme und Formeln zu generieren und zu gucken, ist da vielleicht was Neues, was Interessantes dabei, was noch nicht in der OES als Formel existiert oder als.

8:06Thomas Kahle Ja, und aus der Perspektive der theoretischen Informatik raus, würde man jetzt vielleicht erstmal eine Sprache definieren, in der man die Lösung sucht. Also wie würde denn die Lösung, die Formel oder das Programm, was jetzt die Folge beschreibt, formuliert werden? Ist das ein schwieriges Problem, das erstmal festzulegen oder ist das irgendwie offensichtlich und man muss es nur machen oder wie kommt man jetzt darauf, was die richtige Sprache ist, in der man seine Lösung ausdrückt?

8:36Christian Krause Genau, das hängt ja zum einen damit ab, welche Ausdrucksstärke man haben möchte, was man, welcher Klassen von Funktionen oder Zahlenfolgen man damit potenziell abbilden will. Natürlich allgemein, wenn man jetzt ein Beispiel, ein Sample von einer Zahlenfolge hat, kann man natürlich beliebig da auch eine Kurve oder ein Polynom reinlegen, um da eine Definition rauszugenerieren.

9:00Christian Krause Aber das ist eigentlich nicht Sinn und Zweck, weil letztendlich will man ja im Prinzip eine möglichst sinnvolle und kompakte Beschreibung von der Zahlenfolge haben. Und den Weg, den wir in Loda gegangen sind, ist im Prinzip jetzt keine, ich sag mal. Klassisch jetzt eine Rekursionsgleichung oder andere Formalismen zu nehmen, wo man im Prinzip nur eine Liste von Koeffizienten vielleicht, von einem Polynom hat oder wie auch immer, sondern tatsächlich ein ausführbares Programm zu generieren.

9:29Christian Krause Das syntaktisch sehr einfach aufgebaut ist. Das ist letztendlich eine Folge von Operationen, arithmetischen Operationen, die auf so im Prinzip einem vorgegebenen Speicher arbeiten und dann im Prinzip dort Speicherzellen quasi manipulieren können. Ja, das heißt, wir können Sachen addieren und von links nach rechts schieben und das ist die Grundlage und diese Art von Programmen können wir halt mit verteiltem Rechnen, also im Prinzip mit viel Computerpower zufällige Programme mehr oder weniger generieren und dann im Prinzip mit der Datenbank abgleichen und so Programme finden.

10:07Thomas Kahle Ja, also man hat jetzt erstmal eine Einschränkung. Also es ist deutlich weniger mächtig, dieses Berechnungsmodell oder diese Sprache, als jetzt einfach eine normale Programmiersprache oder so. Natürlich könnte ich ja auch meine Formel irgendwie in Python versuchen anzugeben, aber dann hätte ich zwar eine mächtigere Sprache, aber den Nachteil, dass ich so mächtig bin, dass diese Suche nach einem geeigneten Programm halt nicht mehr automatisiert werden kann oder zumindest nicht mehr sinnvoll automatisiert werden kann. Kann man das so sagen?

10:35Christian Krause Letztendlich in Python kann man ja alles machen, aber letztendlich auch ist es im Prinzip eine Sprache, mit der man ja beliebige Probleme bearbeiten kann, also Anwendungen schreiben kann. Loda, die Sprache selbst, ist wirklich nur jetzt dafür ausgerichtet, für dieses spezielle Problem, wirklich arithmetische Operation.

10:52Christian Krause Ein anderer Aspekt davon ist, wenn man zufällige Programme generiert, ist natürlich zum einen halt wichtig, dass die dann auch terminieren. Wir möchten dann natürlich auch, dass die... Die Programme, die, wenn sie ausgeführt werden, letztendlich auch dann sinnvoll in einer Zahlenfolge dann auch ausspucken, sage ich mal. Dafür ist halt wichtig, dass die terminieren.

11:11Christian Krause Das ist halt in die Sprache mit eingebaut direkt. Und zum anderen, ein anderer Aspekt ist, durch den Prozess, den wir halt machen, wir generieren sehr viele Programme und führen sehr viele Programme aus, haben wir da im Prinzip so einen interpretierenden Ansatz. Das heißt, wir wollen jetzt nicht erst das Programm, den Source, den Quellcode kompilieren und dann im Prinzip ausführen, sondern es würde viel zu viel Overhead sein, weil wir im Prinzip sehr viele Programme durchtesten müssen.

11:38Thomas Kahle Ja, und wenn du sagst, es terminiert das Programm, dann gibt es den Anfang von der Sequenz, für das es steht, aus oder ein vorgegebenes Folgenglied?

11:50Christian Krause Ein vorgebenes Folgenlied. Das heißt, man gibt das Argument für n im Prinzip als Input und bekommt dann a von n, also sprich den Wert der Zahlenfolger an dieser Stelle heraus. Und da garantiert die Sprache im Prinzip Terminierung. Das heißt, wir können sicherstellen, dass es zumindest formal theoretisch terminiert für jedes Folgenlied.

12:16Christian Krause Auf der praktischen Seite müssen wir trotzdem aber eine obere Grenze setzen, was die Anzahl der Ausführungsschritte angeht oder die Ausführungszeit, weil wir natürlich nicht beliebig warten wollen.

12:24Thomas Kahle Also es gibt ja in der Schule, Grundschule sag ich jetzt mal so, manchmal diese Aufgaben, wie geht die Zahlenfolge weiter, ja, also einfach so kleine Logikaufgaben, wo man irgendwie selbst in seinem Kopf das machen soll, was Loda jetzt vielleicht auch macht. Und dann gab es immer so Schlauberger in meiner Klasse, ich habe jetzt immer nicht so dazugezählt, aber die haben dann so, da war die Folge 2, 4, 6, 8 und man sollte das irgendwie fortsetzen und dann haben die halt geschrieben 0, 0, 0, 0 und dann war die Lehrerin hat halt versucht, dann da, gegen zu argumentieren, hat gesagt, naja, also setz die Folge fort und gib die Bildungsvorschrift an und dann haben die die Bildungsvorschrift angegeben,

12:57Thomas Kahle naja, erst kommt 2, 4, 6, 8 und danach geht es immer mit 0 weiter. Wie kann man jetzt bei so Programmen oder vielleicht sogar der automatischen Suche nach Programmen verhindern, dass diese, also irgendwie kommt mir so vor, als ob es so eine menschliche Intuition gibt, was ein sinnvolles Programm ist und was so eine triviale Lösung ist, die das vielleicht auch die Anforderungen erfüllt, aber vielleicht nur den Anfang der Folge abgespeichert hat und dann immer eine Konstante ausgibt oder so.

13:25Christian Krause Ja, das ist natürlich ein Problem und ein valider Punkt letztendlich, kann man ja jede endliche Zahlenfolge beliebig fortsetzen und ein Programm dafür schreiben, aber natürlich ist man interessiert an einer möglichst natürlichen Formel oder Generierungsvorschrift. Und wie man das formal machen kann, ist zum einen braucht man eine gute Datenbasis und die Zahlenfolgen selbst müssen auch eine bestimmte, ich sag mal, Charakteristik oder Signifikanz in den Daten haben.

13:51Christian Krause Also wenn man das jetzt zum Beispiel nur mit zehn Folgen, die da hat und die halt wie in deinem Fall, keine Ahnung, zwei, vier, sechs, acht ist, okay, da könnte man im Prinzip vielleicht noch das Einfache im Prinzip herausfinden. Aber prinzipiell müssen genügend Daten da sein und es muss halt in einer bestimmten Form halt eine bestimmte Signifikanz haben.

14:13Christian Krause Wenn du zum Beispiel sogenannte BT-Sequenzen dir anschaust, die ja im Prinzip letztendlich irgendeine irrationale Konstante multipliziert mit n, da kannst du auch letztendlich 10.000 Folgen, die da haben und das trotzdem sehr gut mit einer linearen Funktion, mit einem rationalen Koeffizienten approximieren.

14:31Christian Krause Das geht schon. Und deswegen sind solche Arten von Zahlenfolgen schlecht geeignet für diesen Prozess. Aber andere Zahlenfolgen, keine Ahnung, die jetzt mehr vielleicht aus dem Bereich Zahlentheorie kommen, keine Ahnung. Basierend auf den Anzahlen der Divisoren etwas machen oder basierend auf Primzahlen, da hast du eigentlich in der Regel genug Signifikanz in den Daten drinne, Charakteristik, um da im Prinzip dann ein sinnvolles Programm zu generieren.

14:59Thomas Kahle Und wenn ich jetzt eine arithmetische Progression, eine ganz einfache eingeben würde, also immer nur jede dritte Zahl, sagen wir mal 100 Stück davon, wäre es jetzt so rein empirisch gesprochen das, was Loda ausrechnen würde? Also das Programm, was einfach sagt immer, okay, rechne dreimal n bei der arithmetischen Progression jetzt einfach dreimal n.

15:18Christian Krause Das würde Loda auch so ausspucken. Und die Frage ist natürlich, wie kommt es halt da drauf und jetzt nicht nur irgendeinen Unsinn noch daneben machen. Es können mehrere Programme halt für die gleiche Sequenz generiert werden. Und dann wird das Bessere im Prinzip ausgesucht und in die Datenbank eingepflegt.

15:35Christian Krause Und wie das in Loda definiert ist, ist die Entscheidung im Prinzip so, dass wir halt gucken, was die Ausführungskomplexität, also wie viele Schritte braucht die Ausführung. Und in dem Fall, wenn das eine einfache arithmetische Progression ist, kommst du halt mit einer einfachen Multiplikation, ist das die minimale Anzahl von Schritten und dadurch hast du im Prinzip schon das Programm definiert.

15:56Thomas Kahle Okay, dann habe ich auch noch gesehen, dass der Befehlssatz in Loda auch ermöglicht, auf eine andere OIS-Folge zurückzugreifen. Also das ist so ein standardprimitiver Befehl, wenn ich jetzt eine Folge hätte, die einfach eine andere Folge ist plus eine Konstante, würde das dann auch gefunden werden, oder ….

16:17Christian Krause Das würde auch gefunden werden, wobei diese Operation bedeutet letztendlich nicht, dass wir im Prinzip die Daten der anderen Sequenz mit einarbeiten, sondern es ist letztendlich ein Aufruf eines anderen Programmes. Das heißt, wenn wir, keine Ahnung, für die Fibonacci-Zahlen, das ist glaube ich die, was ist das, die A45, die referenzieren in einem Loda-Programm, dann würde im Prinzip unter der Haube das Programm ausgeführt werden, was für die Fibonacci-Zahlen steht.

16:47Thomas Kahle Ja, ergibt Sinn. Und könnte man es jetzt zum Beispiel, es gibt so einen Nutzer auf Mastodon, das ist mein Lieblings-Social-Network, Christian Lawson Perfect, der hat auch so Blogs, Aperiodical und so, so ein relativ bekannter Mathematiker aus England, der auch viel Mathematikkommunikation macht und der macht öfter so Rätsel.

17:06Thomas Kahle Das stellt ja so eine Zahlenfolge und ich glaube, da gibt es auch meistens so 20 bis 50 Zahlen an, die es noch nicht in OIS gibt und dann raten die Leute, was die Bildungsvorschrift ist. Meinst du, dass man mit Loda da irgendwie in diesem Wettbewerb teilnehmen könnte?

17:19Christian Krause Ein Versuch ist auf jeden Fall wert. Ich kenne das nicht. Wäre natürlich interessant, das mal auszuprobieren. Also letztendlich, es fließen ja auch immer, es kommen ja auch immer neue Sequenzen dazu in die OIS. Und was man beobachten kann, ist letztendlich, dass viele von denen auch ähnlicher, ähnlich aufgebaut sind.

17:37Christian Krause Im Prinzip Variation von einer Klasse von Funktionen und Zahlenfolgen. Und speziell jetzt in den Fällen, wo es halt schon, ich sag mal, ähnliche Folgen gibt, nicht jetzt, was die Werte angeht, aber im Prinzip, wie sie definiert sind, dann kann man sehr schnell, oder dann findet Loda sehr schnell da Programme für.

17:55Christian Krause Ja, ich weiß aber nicht, wie die Rätsel dort aufgebaut sind und wie weit entfernt das von einem Prinzip von Zahlenfolgen in der OES ist.

18:03Thomas Kahle Ja, ich habe da jetzt auch nicht so viel mitgemacht, deswegen weiß ich es auch nicht, aber ich hätte jetzt Lust, das mal auszuprobieren. Können wir ja im Nachgang nochmal machen. Wie ist das als eine Open-Source-Software? Also ich kann mir sozusagen, wenn ich mir Loda runterlade, was habe ich dann? Also dann habe ich einen Interpreter oder für Loda-Programme?

18:22Christian Krause Genau, es gibt verschiedene Teile, wie es gibt letztendlich ein Kommandoteil-Tool, was man sich runterladen kann. Mit dem kann man sowohl existierende Programme ausführen, interpretieren, als auch diese Suche machen. Wir haben aber auch gleichzeitig, dadurch, dass es verteiltes Rechnen letztendlich ist, benutzen wir auch zusätzlich noch eine verteilte Infrastruktur für verteiltes Rechnen. Das nennt sich Boing.

18:46Christian Krause Von der Berkeley University als im Prinzip Abspaltung von dem SETI-Atom-Projekt. Ich weiß nicht, Anfang der 2000er Jahre war das?

18:54Thomas Kahle Ja, möchte ich sagen, dass ich das auch schon mal erwähnt habe. Es gab so verschiedene Bildschirmschoner-Programme, die so Citizen Science gemacht haben. Über Boink bin ich ja auch auf Loda aufmerksam geworden. Ich habe da mal so die Mathe-Projekte durchgeguckt. Eigentlich war dieses Prime Grid, also die Suche nach den Primzahlen und Faktorisierungen von irgendwelchen großen Zahlen, weil die immer so scharfe Deadlines hatten.

19:15Thomas Kahle Also da musste man immer so seine Arbeit sofort, muss man einen richtig guten Computer und muss das immer sofort einreichen. Und da habe ich auch mal so geschaut, was da noch so für Mathe ist und so bin ich dann auf Loda eigentlich gestoßen. Und ja, also habt ihr 2022 oder so, habe ich gelesen, ihr angefangen dann eure Suche nach Programmen über dieses Boink an Freiwillige überall auf der Welt zu verteilen, richtig?

19:36Christian Krause Genau, es ging vorher auch schon verteilt, aber natürlich dann nur in so einer kleinen Community mit so ein paar einzelnen Leuten. Durch dann den Einsatz von Boeing auf diese Infrastruktur ist es deutlich mehr geworden, wobei ich aber auch sagen muss, davor hatten wir auch so, hatte ich auch Kontakt zu zum Beispiel dem Autor, der hinter der Online-Plattform Sequence Machine, ich glaube früher ist es SequenceDB steht, Kontakt.

20:05Christian Krause Der hatte recht leistungsstarke Hardware und hatte da auch Luder laufen lassen, hätte auch viel gefunden. Aber genau, mit dem Schritt auf die Boeing-Infrastruktur haben wir das natürlich deutlich mehr verteilen können. Und heutzutage, ja, letztendlich dieser Boeing-Client, man lädt den sich runter und dann kann man sich im Prinzip aussuchen, für welches Projekt möchte man Rechenkapazität zur Verfügung stellen.

20:27Christian Krause Und dann läuft das im Hintergrund wie so ein Bildschirmschoner, wie du schon sagst.

20:30Thomas Kahle Und was für eine, kann man das irgendwie beziffern, was für eine Rechenleistung du da angezapft hast und hat das das dann aufs nächste Level gehoben oder war der eine Collaborator, den du mit der vielen Hardware kanntest, war der dann immer noch der Top-Contributor?

20:46Christian Krause Na, es hat es schon auf einen, so aktuell ist es vielleicht, kann man so sagen, so 1000 Cores, die da so drauf laufen, wobei das auch schwankt. Wir hatten auch Peak-Zeiten, wo es so Richtung 2000, 3000 Cores ging. Genau, und das ist jetzt aber relativ stabil, manchmal ist es mehr, manchmal ist es weniger.

21:06Thomas Kahle Okay, und dann sammelst du diese ganzen Versuche irgendwie ein oder die senden dann alle ihre Ergebnisse ein und was kommt dann danach? Gibt es da noch irgendwie so eine Art Validierung oder eine Auswertung? Also es geht ja darum, jetzt für jede Folge in OIS, jede, sagen wir mal, die geeignet ist, die jetzt nicht zu kurz ist oder so, das natürlichste oder beste Programm, zumindest aus der Sicht von Loda oder in diesem Modell, zu finden.

21:34Thomas Kahle Und die würdest du dann auch dokumentieren. Ich habe ja auch gesehen, dass du einige schon Einträge, also dass du auch ein OIS-Kommentator sozusagen bist mit Formeln und Programmen.

21:46Christian Krause Genau, was im Hintergrund dann abläuft, letztendlich werden die lokal gesucht. Jeder Computer, der dort beteiligt ist an der Suche, hat eine Kopie von den aktuell verfügbaren oder aktuell gefundenen Programmen und kann damit im Prinzip auch direkt schauen, gibt es dafür für diese Sequenz schon ein Programm oder nicht.

22:05Christian Krause Und wenn es schon eins gibt, ist das, was ich jetzt vielleicht gefunden habe, besser. Und wenn dann halt was gefunden wird, dann werden die halt an einen Server geschickt. Und der Server macht nochmal eine grundlegende Validierung und fügt die dann letztendlich in das Repository. Das ist ein GitHub-Repository, wo alle Programme drinstehen, fügt das mit hinzu.

22:26Christian Krause Und das Nette dort ist eigentlich an dem GitHub-Repository, dass man da auch die Historie sieht von den Programmen. Da kann man teilweise dann auch sehen, wie Programme letztendlich immer bessere Versionen von Programmen mit dazugekommen sind oder Programme überschrieben wurden mit besseren Versionen.

22:42Christian Krause Und genau, so funktioniert das.

22:45Thomas Kahle Genau, und da hatte ich auch irgendwie, ich weiß nicht, ob es jetzt schon wieder raus ist, ob es schon wieder überholt wurde, aber irgendwie hatte ich dann sogar tatsächlich meinen Computer oder meinen Nickname da durch Suche in dem GitHub-Repository gefunden, aber die Folge kannte ich leider nicht, war mir ein bisschen schade, aber es war jetzt nicht so, dass es irgendeine Star-Folge, also mein Computer hat keine neue Formel für die Fibonacci-Numbers gefunden oder so, aber naja, es gibt ja auch verschiedene Folgen.

23:10Christian Krause Genau. Ja, das eine ist, das möchte ich auch erwähnen, dass letztendlich für jedes Programm, was dann im Prinzip, wenn man schon seine Rechenkapazität zur Verfügung stellt, kann man seinen Namen letztendlich in den Programm mit dort angeben. Das wird da mit eingefügt. Das heißt, wenn man was gefunden hat, dann kann man sich auch verewigen in der Datenbank.

23:32Christian Krause Und zum anderen, die Boing-Infrastruktur selbst bietet im Prinzip auch letztendlich Statistiken darüber an, wie viel Rechenkapazität man dort reingesteckt hat. Und das ist tatsächlich für viele Leute, die dort beteiligt sind oder überhaupt, die an Boing-Projekten teilnehmen, ein wichtiger Aspekt. Also im Prinzip dort zu sehen, wie viel Kapazität sie reingesteckt haben.

23:52Thomas Kahle Mhm. Ergibt es irgendwie Sinn, das auf Grafikkarten laufen zu lassen oder ist das eigentlich so eine ganz typische CPU-Sache?

23:59Christian Krause Diese Anfrage kommt immer wieder und kam auch schon oft aus der Boeing-Community. ist schwierig. Also ich habe es nicht hinbekommen bisher. Ich habe es auch noch nicht wirklich versucht jetzt zu implementieren direkt, weil ich letztendlich bin auch kein Experte, muss ich ehrlich sagen, jetzt was GPU- Programmierung angeht.

24:19Christian Krause Aber der Prozess, wie das, was wir nennen, Mining, im Prinzip diese Programmsuche, aktuell funktioniert, hat eine bisher für mich zu hohe Komplexität, als dass man das auf eine GPU abbilden könnte. Vielleicht mit einem geeigneten Experten könnte man das probieren, aber ich habe es bisher noch nicht hinbekommen.

24:38Thomas Kahle Ja, du hast ja auch ein paar Mal wir gesagt, also ist das jetzt so ein Team, größeres Team? Also ich habe gesehen, ihr habt einen Discord, bin auch gestern mal beigetreten und habe so ein paar alte Nachrichten durchgescrollt, aber was für ein Team steckt dahinter oder hast du es jetzt im Wesentlichen programmiert?

24:53Christian Krause Ja, also im Wesentlichen habe ich die größten Teile davon programmiert. Wir haben andere Teile auch noch, letztendlich auch einen Web-Editor, einen Interpreter in einem Browser, Und letztendlich auch eine alternative Implementierung von der Suche, einer anderen Programmiersprache. Die läuft nicht auf Boing, kann man aber lokal ausführen. Und das hat ein Mensch in Dänemark gemacht.

25:18Christian Krause Und es gibt noch so ein paar, ein, zwei weitere Contributor, aber ich bin schon der Hauptentwickler da.

25:24Thomas Kahle Und es gibt jetzt aber keine Veröffentlichung. Also wenn ich mir das so jetzt anhöre, denke ich, es gibt ja so Journale in der Mathematik, irgendwie Experimental Mathematics gibt es zum Beispiel. Oder auch, ja, also welche, die sich irgendwie auf Daten beziehen, Bezüge zur Informatik haben. Also es gibt jetzt keine wissenschaftliche Veröffentlichung bisher, die du da irgendwie zugemacht hast?

25:46Christian Krause Nee, gibt bisher keine Veröffentlichung, steht noch auf der To-Do-Liste, aber bisher bin ich nicht dazugekommen. Ich muss auch sagen, ich meine, ich habe das jetzt, dadurch, dass ich nicht mehr in der Forschung bin, ist das jetzt auch nicht für mich spielentscheidend oder wie auch immer. Aber natürlich, ja, es wäre das schön, irgendwie nochmal zu haben.

26:04Christian Krause Vielleicht kommt es nochmal, wenn ich vielleicht auch geeignete Kollaboratoren finde. Aber bisher bin ich noch nicht dazugekommen.

26:10Thomas Kahle Ja, also ich finde das überhaupt, also ich weiß es, ich bin jetzt auch nicht so der Programmierer. Also ich programmiere immer so Hobby-mäßig oder in Computer-Algebra-Systemen. Also was der Aufwand wirklich ist, kann ich nicht einschätzen, aber so von außen sieht das halt schon sehr professionell und aufwendig irgendwie aus, also dieses Projekt zu managen.

26:30Thomas Kahle Also finde ich eigentlich sehr erstaunlich, dass du das in deiner Freizeit noch mitmachen kannst. Das ist eigentlich auch sozusagen Citizen Science in dem Sinne.

26:37Christian Krause Das stimmt. Wobei halt, es ist schon sehr viel sehr stark automatisiert. Das läuft eigentlich im Hintergrund. Das ist relativ wenig manueller Aufwand. Aber das Interessante oder da, wo eigentlich Kapazität reingehen müsste oder fehlt, ist vielleicht Weiterentwicklung. Letztendlich die Kurve an Suchergebnissen, die wird immer flacher.

26:58Christian Krause Man muss immer gucken, wie kann man im Prinzip die Algorithmen, die Sprache oder wie auch immer verbessern, sodass man eine größere Klasse von Zahlenfolgen mit abbilden kann und dort Programme finden kann.

27:10Thomas Kahle Und wenn man jetzt auf das ganze Projekt blickt und sich mal raussucht, was sind eigentlich die Folgen in OES, die dann eine überraschend komplizierte Lösung oder ein überraschend kompliziertes Programm haben, obwohl man ihnen das von außen nicht ansieht. Also gibt es da irgendwelche Überraschungen, dass man jetzt denkt, okay, hier sind zwei Folgen, die sehen eigentlich relativ ähnlich aus, kommen vielleicht aus einem ähnlichen Kontext der Mathematik, aber die eine hat eben im Sinne von diesem Loda so eine sehr hohe Beschreibungskomplexität und die andere eine ganz einfache.

27:48Thomas Kahle Also gibt es irgendwelche so Ergebnisse, die du da gefunden hättest?

27:52Christian Krause Also ganz konkret kann ich, also ich kann ein bisschen, zum einen gibt es halt eine bestimmte überraschende Komplexität bei Sachen, wo man halt, wo es keine Primitiven dafür gibt, wo es relativ aufwendig ist, das zu implementieren mit der Sprache. Aber wir hatten zum Beispiel lange Zeit keine binären Operatoren drin.

28:15Christian Krause Und dadurch waren die Programme, die relativ mit binären Operatoren auszudrücken sind, relativ überraschend kompliziert, einfach weil die Operatoren gefehlt haben. Das ist so ein Aspekt. Und der andere Aspekt ist, Ist vielleicht allgemein, warum, ich meine, oft lassen sich auch Programme relativ oder Zahlenfolgen relativ einfach definieren, aber dann sind sie oft nicht konstruktiv.

28:41Christian Krause Es ist schon ein Unterschied, ob man jetzt eine Rekursionsgleichung angibt, mit der man im Prinzip jedes Folgendlied hintereinander wegberechnen kann, oder halt eine Zahlenfolge definiert, basierend auf einer Eigenschaft von einer Zahl. Ja, keine Ahnung, wenn du jetzt sagst, die Anzahl der Primzahlen kleiner n, ja, klassisches Beispiel, oder andere Zahlenfolgen, die im Prinzip auf einer bestimmten Eigenschaft von der Zahl basieren, dann ist das einfach zu definieren, aber relativ komplex zu implementieren.

29:09Thomas Kahle Und letztendlich löst das ja vielleicht auch so schwierige Rekursionsprobleme dann on the fly. Wenn ich also eine Zahlenfolge definiere, die ähnlich wie die Fibonacci-Zahlen, aber irgendwie eine komplizierte Linearkombination der letzten fünf Werte nimmt und dann habe ich irgendwie fünf Startwerte, dann eine direkte Formel anzugeben für das Ende-Folgenglied, wird ja dann vielleicht eine hohe Komplexität haben, obwohl es eigentlich nur eine lineare Rekursion ist. Obwohl, da gibt es doch dieses Master-Theorem.

29:34Thomas Kahle Gibt es nicht irgendeine Master-Theorem in der Informatik? Das würde ich ganz lange zurückdenken an irgendwelche Vorlesungen.

29:40Christian Krause Ja, aber diese Art von Zahlenfolgen, die jetzt, ich sag mal, eine relativ einfache Rekursionsgleichung haben, die auf eine fixe Anzahl von vorhergehenden Elementen basieren, das ist relativ einfach in Loda abzubilden und dafür werden im Prinzip Programme auch sofort gefunden. Schwieriger ist es eher, wenn man zum Beispiel eine Zahlenfolge hat, die sich auf alle vorhergehenden Terme bezieht, in einer nicht trivialen Art und Weise.

30:07Christian Krause Genau, da sind die Programme natürlich komplexer.

30:11Thomas Kahle Ja, also das als, jetzt könnte ich dich nochmal fragen, was jetzt sozusagen jetzt nach unserem Gespräch deine Lieblingsfolge ist. Also es gibt ein paar Einträge in OIS, wo dann einfache Formeln, wo du als Mensch per Hand oder so ein Loderprogramm, weil du es lesen kannst, wieder zurück übersetzt hast in eine Formel. Hatte ich das richtig in Erinnerung?

30:30Christian Krause Genau, also da gibt es eine, und zwar hängt das zusammen mit den Primzahlen. Also bei den Primzahlen, da gab es eine relativ lange Historie von Programmen, die letztendlich haben sich immer effizientere Programme dann letztendlich herauskristallisiert.

30:48Thomas Kahle Also bei den Primzahlen würdest du dann die n-te Primzahl ausgeben, ja? Ist ja auch ein interessantes Problem, habe ich noch nie so drüber nachgedacht. Also was ist die Funktion, die die n-te Primzahl ausrechnet? Witzig.

31:00Christian Krause Also bei den Primzahlen, das ist die A40, glaube ich, in der OES, das ist die Zahlenfolge definiert, die gibt die Ente-Primzahl aus. Und bei den Primzahlen ist es ja so ein klassisches Beispiel von einer Definition, die im Prinzip eine Eigenschaft von der Zahl widerspiegelt. Und da ist es letztendlich so, dass man, wenn man das jetzt konstruktiv ein Programm angeben möchte, das die Endprimzahl berechnet, muss man, ist in der Regel die Strategie, dass man letztendlich alle Zahlen prüft, bis zu einer bestimmten Schwelle und dann im Prinzip prüft, ist es eine Primzahl, ja oder nein.

31:40Christian Krause Und basierend darauf gibt es natürlich Primzahltests, die effizienter oder weniger effizienter sind, Und eine Sache, die dann in Loda aufgefallen ist letztendlich, dass im Prinzip ein Programm für die Primzahlen gefunden wurde, das relativ kompliziert war mit drei verschachtelten Schleifen. Und da hat sich dann im Prinzip herausgestellt, dass der innere Teil von dieser Funktion.

32:10Christian Krause Eine charakteristische Funktion war, die es so in der Form in der OES noch nicht gibt und die ich dann im Prinzip im Nachhinein eingefügt habe in die OES, auch vor dem Hintergrund, damit sie dann später in Loda referenziert werden kann und effizient für andere Programme benutzt werden kann. Und das ist die Zahlenfolge A365605 und die nennt sich Characteristic Function of Numbers without an inferior odd divisor greater one.

32:37Christian Krause Und die wird im Loda-Programm für die Primzahlen und auch vielen anderen benutzt und das ist bisher aktuell in Loda die effizienteste Methode, um Primzahlfolgen zu finden.

32:51Thomas Kahle Das ist ja eigentlich witzig. Du hast ja quasi jetzt deine Methode entwickelt, so eine Art Injection in dein Loda-Programm noch machen kannst. Also eigentlich willst du ja wahrscheinlich die Sprache stabil halten, also jetzt keine neuen primitiven Operationen mehr zu deiner Loda-Sprache hinzufügen. Aber was du machen kannst, ist eine Folge zu OES hinzufügen und die dann wieder aufzurechnen. Aber für die brauchst du auch wieder ein Loda-Programm.

33:12Thomas Kahle Also okay, es bringt nichts, weil du nicht einfach die Konstanten aus der OES nimmst, weil dann hast du ja vorhin erklärt, dass der Aufruf einer anderen Folge eigentlich eine andere Subroutine aufruft. Also doch nicht. Kein Sicherheitsrisiko jedenfalls in Loda.

33:26Christian Krause Nee, ein Sicherheitsrisiko ist es nicht. Also am Anfang, als ich damit angefangen habe, hatte ich das schon versucht, den Sprachsatz irgendwie minimal zu halten. Aber da bin ich schnell an Grenzen gestoßen. Und deswegen ist jetzt eigentlich eher der Ansatz zu gucken, ja, solange, also auch, wenn es sinnvoll ist, der Operation hinzufügen, dann füge ich die auch hinzu. Vorausgesetzt, die sind...

33:46Christian Krause Effizient berechenbar. Das heißt, ich würde jetzt zum Beispiel nicht in eine Operation einfügen, die die Ente-Prime-Zeit berechnet, weil das ist ein algorithmisch komplexes und aufwendiges Problem und das ist eigentlich nicht Ziel, sondern es geht im Prinzip darum, letztendlich nur effiziente Operationen da zu benutzen.

34:06Thomas Kahle Ja, ergibt sehr viel Sinn. Sehr schön. Ja, also so meine Liste habe ich hier so ein bisschen durch. Blick auf die Uhr sagt auch, dass wir gut in der Zeit liegen. Wir verlinken natürlich das GitHub, eure Projektwebseite oder deine Projektwebseite und OES-Einträge, die wir heute erwähnt haben. Gibt es noch irgendwas, was du mitgeben möchtest den Hörerinnen und Hörern?

34:28Thomas Kahle Also ich denke mal, Beiträge zu dem Boink-Projekt sind immer gern gesehen. Aber noch irgendwas anderes?

34:33Christian Krause Ja, wer es ausprobieren möchte, kann sich gerne den Boink-Client installieren oder mal auf die Webseite schauen. Und ja, wer interessiert ist, kann sich auch gerne auf den Kanälen melden, auch vor allem, wer interessante Vorschläge hat, wie man die Sprache erweitern kann oder andersweitig da interessante Projekte daraus ableiten kann, können sich gerne melden.

34:54Christian Krause Genau, es gab auch interessante, ich sag mal, Mini-Kollaborationen in der Vergangenheit auch schon, wo wir auch so ein bisschen geschaut haben, wie kann man AI-Methoden, generative AI-Methoden benutzen vielleicht, um da Programme zu generieren. Also es gibt viele spannende, interessante Ideen und wer Lust hat, meldet sich gerne.

35:10Thomas Kahle Ja, hast ja jetzt nochmal, jetzt hast du quasi im letzten Satz nochmal ein ganz neues Thema aufgemacht. Es ist natürlich auch interessant, die Machine Learning da in Stellung zu bringen. Aber ja, ich würde sagen, das lassen wir dann für unsere nächste Folge, die wir zu OES machen. Wenn du was hast, sag Bescheid, dann lade ich dich nochmal ein.

35:30Christian Krause Sehr gerne, danke für die Einladung.

35:32Thomas Kahle Also mach's gut, tschüss.