Thomas Kahle
Christian Krause
Heute ist Christian Krause zu Gast und wir sprechen über die LODA-Programmiersprache. Diese einfach gehaltene Assembly-Sprache dient dazu, kurze und effiziente Programme zu finden, die Zahlenfolgen erzeugen können, bspw. solche in der OEIS. Eine Besonderheit an LODA ist, dass die Programme automatisch gesucht werden können. Man nennt das „Mining“. Die Suche nach den besten Programmen hat Christian über die BOINC Infrastruktur als distributed computing Projekt aufgesetzt.
- LODA auf github
- LODA im Web
- LODA Programme für OEIS Folgen
- BOINC distributed computing
- Beatty Sequence
- Christian P erfindet eine neue OEIS Folge — als Rätsel
- Sequence Machine (formerly SequenceDB)
Feedback gerne auf Mastodon @Eigenraum@podcasts.social, an feedback (bei) eigenpod.de oder in die Kommentarspalte auf der Episodenseite.
Automatisch generiertes Transkript (nicht geprüft)
Thomas 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.
Christian Krause
Hallo Thomas, danke für die Einladung.
Thomas 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?
Christian 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.
Thomas 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?
Christian 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.
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.
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.
Und da angesiedelt ist natürlich die UES als im Prinzip Datenbank für Zahlenfolgen.
Thomas 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.
Ja, hast du eine Lieblingsfolge in der OIS oder kann man es so nicht sagen?
Christian 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.
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.
Aber um deine Frage zu beantworten, nee, ich habe jetzt keine spezielle oder Lieblingsfolge.
Thomas 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.
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.
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.
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.
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?
Christian 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.
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.
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.
Thomas 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.
Sind auch diese und diese Zahlen, die in irgendwelchen anderen Kontexten aufgetreten sind.
Christian 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.
Thomas 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?
Christian 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.
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.
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.
Thomas 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?
Christian 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.
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.
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.
Thomas 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?
Christian 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.
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.
Thomas 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,
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.
Christian 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.
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.
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.
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.
Thomas 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.
Christian 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.
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.
Thomas 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 ….
Christian 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.
Thomas 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.
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?
Christian 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.
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.
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.
Thomas 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?
Christian 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.
Von der Berkeley University als im Prinzip Abspaltung von dem SETI-Atom-Projekt.
Ich weiß nicht, Anfang der 2000er Jahre war das?
Thomas 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.
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?
Christian 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.
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.
Und dann läuft das im Hintergrund wie so ein Bildschirmschoner, wie du schon sagst.
Thomas 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?
Christian 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.
Thomas 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.
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.
Christian 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.
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.
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.
Und genau, so funktioniert das.
Thomas 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.
Christian 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.
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.
Thomas Kahle
Mhm. Ergibt es irgendwie Sinn, das auf Grafikkarten laufen zu lassen oder ist
das eigentlich so eine ganz typische CPU-Sache?
Christian 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.
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.
Thomas 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?
Christian 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.
Und es gibt noch so ein paar, ein, zwei weitere Contributor,
aber ich bin schon der Hauptentwickler da.
Thomas 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?
Christian 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.
Vielleicht kommt es nochmal, wenn ich vielleicht auch geeignete Kollaboratoren
finde. Aber bisher bin ich noch nicht dazugekommen.
Thomas 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.
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.
Christian 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.
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.
Thomas 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.
Also gibt es irgendwelche so Ergebnisse, die du da gefunden hättest?
Christian 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.
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.
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.
Thomas 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.
Gibt es nicht irgendeine Master-Theorem in der Informatik?
Das würde ich ganz lange zurückdenken an irgendwelche Vorlesungen.
Christian 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.
Genau, da sind die Programme natürlich komplexer.
Thomas 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?
Christian 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.
Thomas 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.
Christian 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.
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.
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.
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.
Thomas 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.
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.
Christian 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...
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.
Thomas 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?
Also ich denke mal, Beiträge zu dem Boink-Projekt sind immer gern gesehen.
Aber noch irgendwas anderes?
Christian 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.
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.
Thomas 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.
Christian Krause
Sehr gerne, danke für die Einladung.
Thomas Kahle
Also mach's gut, tschüss.