welle::erd.ferkel

Jetzt, wo gerade die Collatz-Vermutung auch durch Mainstream-Medien geistert, fragen immer wieder Leute:

Wozu braucht man das überhaupt?

Na, zum Beispiel um verdammt hinterhältige reguläre Ausdrücke zu bauen. (Und auch gelegentlich, wenn man nicht genug Bauteile für eine Turing-Maschine rumliegen hat. Zum Beispiel da, oder dort.)

Ganz viele Sachen, sowas von in Kürze!

Ich war fort; bald bin ich wieder da. Bis dahin können sich jene, die glauben, “reguläre” Ausdrücke zu beherrschen, sich die Zeit mit einem Rätsel vertreiben.

Für n≥2, definieren wir die regex rx(n) im Python-Dialekt als

^(((ba{n-1}b[ab]*)|(ba{n+1}[ab]*)|(a[ab]*)|([ab]*a)|([ab]*bb[ab]*)|(b)|([ab]*aab)|([ab]*b(aa)*ab(aaaaaa)*(()|(a|aa|aaa|aaaaa))b[ab]*))|([ab]*b(?P<x>(a*))(((?P=x)b(?P=x)a)|((?P=x)ab(?P=x){6}aaaaa)|((?P=x)(aa)+b(?P=x)b)|((?P=x)(aa)+ab(?P=x){6}aaaab))[ab]*))$

Hierbei sind in {n-1} und {n+1} natürlich durch die entsprechenden Zahlen einzusetzen; rx(3) ist zum Beispiel

^(((ba{2}b[ab]*)|(ba{4}[ab]*)|(a[ab]*)|([ab]*a)|([ab]*bb[ab]*)|(b)|([ab]*aab)|([ab]*b(aa)*ab(aaaaaa)*(()|(a|aa|aaa|aaaaa))b[ab]*))|([ab]*b(?P<x>(a*))(((?P=x)b(?P=x)a)|((?P=x)ab(?P=x){6}aaaaa)|((?P=x)(aa)+b(?P=x)b)|((?P=x)(aa)+ab(?P=x){6}aaaab))[ab]*))$

Die eigentliche Frage ist: Für welche n beschreibt rx(n) genau die gleichen Wörter wie der Ausdruck ^[ab]+$ ? Oder, was kurioserweise eine leichtere Frage ist: Welche Wörter beschreibt rx(n) denn überhaupt für ein bestimmtes n?
Tip: Diese Frage stellt man sich besser umgekehrt — welche Wörter aus der vom Ausdruck ^[ab]+$ beschriebenen Sprache werden nicht von rx(n) beschrieben?

Zugegeben, die erste Frage ist gemein, da selbst Onkel P. kapitulierte, aber an der zweiten kann man sich versuchen.

Wer die benannten Rückreferenzen im Python-Stil nicht mag (z.B. Leute, die jüngeres Perl als 5.10 verwenden) kann die Ausdrücke übrigens auch gerne auf klassische Rückreferenzen umschreiben — man schmeiße dazu einfach das ?P raus, zähle Klammern, und ersetze die ?P=x entsprechend durch \17 oder so etwas. Einfacher ist’s, wenn man

^(([ab]*b(a*)((\3b\3a)|(\3ab\3\3\3\3\3\3aaaaa)|(\3(aa)+b\3b)|(\3(aa)+ab\3\3\3\3\3\3aaaab))[ab]*)|((ba{n-1}b[ab]*)|(ba{n+1}[ab]*)|(a[ab]*)|([ab]*a)|([ab]*bb[ab]*)|(b)|([ab]*aab)|([ab]*b(aa)*ab(aaaaaa)*(()|(a|aa|aaa|aaaaa))b[ab]*)))$

schreibt, dann findet man aber {n-1} und {n+1} nicht mehr so leicht.

Rückfragen sind im Kommentarbereich gerne gesehen; ich will ja nicht, dass am Ende alles an etwaigen Tippfehlern meinerseits scheitert.

Das Zitat dort stammt, wie viele sich vielleicht bereits gedacht haben, aus dem Aufregerbuch der Saison. Anders als viel zu viele, die darüber reden, habe ich mir die Mühe gemacht, jenes zu lesen — unaufgeregt, wenn auch mit der leisen Vorahnung, mich zu langweilen.

Continue reading "Noch eine Lösung" »

Manch eine wird sich vielleicht noch erinnern — vor fast einem Jahr fragte ich hier nach einem obskuren Buch. In Erfüllung meines Bildungsauftrags wiederhole ich hier den Hauptteil des Rätsels, die Lösung und Erklärungen diverser obskurer Hinweise sind verlinkt, so dass man (wenn man die nötige Disziplin hat) raten kann, welche Hinweise wie zur Lösung passen:

In der Tat ist dieses Buch so relevant, dass es sogar einen Eintrag in der selektiven deutschsprachigen Wikipedia hat (derzeit zumindest); und mit einem der (sogar titelgebenden) Themen beschäftigte sich nicht nur Ha-Ha-Hannah vor dem schicksalhaften Anruf, sondern auch (zum Beispiel) Marx. Anderes des gleichen Autors inspirierte ebenfalls, zum Beispiel eine Band, die ich vor kurzem nicht gesehen habe, da ich es — müde und überarbeitet — vorzug, zu schlafen, statt ins Bett zu gehen.

Wie Haha, Jaja, und Backenbuckel mit dem Hammer zusammenpassen sollte nun allen klar sein.

Woher stammt das folgende provokative Zitat?

Während der Zugang zu Sprache, Kultur und Kunst – in unterschiedlichen Graden natürlich – allen Menschen möglich ist, die mit einer gewissen Grundintelligenz ausgestattet sind, gilt das für die Mathematik und die Naturwissenschaften nicht; ihr Charakter setzt ein bestimmtes formales Verständnis voraus, sonst ist der Zugang quasi digital versperrt. Das weiß jeder Schüler, der einmal bei einer mathematischen Ableitung an der Tafel gescheitert ist.

Bevor jemand auf falsche Gedanken kommt — ich sehe das ganz gewiss nicht so. Sicherlich hilft Talent, aber formales Verständnis ist vor allem eine Frage der Übung (jahrelanger Übung, aber Übung). Und der Einstellung. “Mathematische Ableitungen” sind (in der schulüblichen Form, wie eigentlich die ganze Schulmathematik) nahezu immer durch stures Auswendiglernen einiger Tricks zu bewältigen; Verständnis ist hierbei zwar hilfreich, aber nicht notwendig.

Allerdings ist der Autor auch Politologe und somit (seiner Meinung nach) sowieso nicht in der Lage, zum mathematisch-naturwissenschaftlichen Fortschritt beizutragen…

Diverse Beantwortungen in Kürze! Dies gilt besonders für interkontinentale Emails, die schon viel zu lange liegen. Also, die eine.

Nachdem ich die 150 Seiten von Kapitel X von Odifreddis Classical Recursion Theory, Volume II überflogen habe, finde ich endlich den Beleg für meine Vermutung und kann so der Frage des verrückten Russen ein herzhaftes “Vollständig für Σ₂⁰ bzw. Π₂⁰, ha!” entgegenschleudern. Höhergradige Unentscheidbarkeit, exakt positioniert — und das in meinem Urlaub.

Ebenfalls dort endeckt: Die monster injury priority method, Gerüchten zufolge auch in der vierten Auflage von D&D enthalten. (Ist laut Buch verwandt mit no-injury priority method, finite injury priority method und infinite injury priority method. Naheliegend vermute ich die Existenz von double-, mega- und ultra-Varianten der injury priority method zusätzlich zur m-m-m-monster injury priority method, so von wegen injury priority method spree.)

Es ist immer wieder erfrischend festzustellen, wie wenig man doch von Dingen weiß, von denen man wenigstens einen groben Überblick zu haben glaubte.