welle::erd.ferkel

Liest jemand von euch XKCD? Ich hatte das mal in meiner Feedsammlung, habe dann aber festgestellt, dass alle Folgen, die mir gefallen, sowieso in allen möglichen Blogs zitiert werden. Leider nicht nur die, aber so bleiben mir die eher unheimlichen Folgen (z.B. die, oder die) erspart, ohne dass ich gelegentliche interessantere Folgen verpasse¹. Nun, jedenfalls, kürzlich gab’s dort eine vielzitierte Folge über einen Typen, der in einer unendlichen Ebene mit unendlich vielen Steinen ein unendlich ödes Leben verbringt. Nach einiger Zeit beginnt er, das Universum mit einem Zellularautomaten zu simulieren, der eine universelle Turingmaschine simuliert.

Das geht zwar im Prinzip, ist aber nicht das, was ich machen würde — viel praktischer wäre es, stattdessen eine universelle addierende Minsky-Maschine mit zwei Registern² zu simulieren. Die kodiert ihre Konfiguration nämlich nicht in einem String unbeschränkter Länge, sondern in zwei natürlichen Zahlen und einem Zustand. Die Zahlen stellt man durch zwei Haufen dar, und den Zustand merkt man sich, denn da braucht man nur wenige verschiedene.

Wer will schon eine schrecklich lange Reihe von Steinen und Lücken, bei der man sich noch dazu penibel an Abstandskonventionen halten muss, wenn zwei simple Haufen genau das gleiche ausdrücken können? Wenn man unbedingt Steine umschichten will genügt sogar ein einziger Haufen, denn eine mulitplizierende Minsky-Maschine braucht zur Universalität nur einen Zähler.

Unendlichkeit ist keine Entschuldigung für Ineffizienz — EIN HAUFEN IST GENUG!

¹ Apropos, das hier. Nobody Scores! ist sowieso empfehlenswert, hatte bisher keine einzige doofe Depri-Folge und ist sogar richtig gezeichnet. Ich hoffe nur, dass es nun nicht wie Dresden Codak (wir erinnern uns, Dungeons and Discourse) kurz nach meinem gebloggten Lob zu stinklangweiliger Singulolitätsgrütze verkommt.

² Grob erklärt ist das ein Computer mit zwei Speicherzellen, die (beliebig große) natürliche Zahlen fassen können. Die Maschine überprüft in jedem Befehlsschritt, ob die Zähler 0 enthalten und kann dann einen bedingten Sprung ausführen und die Zähler um jeweils 1 verändern. Details sowie Beweis der Turingvollständigkeit dort. Wie man so etwas ähnliches in einem nichttrivialen Beweis benutzen kann sieht man zum Beispiel dort.

Es ist kein Schmalztiegel, es ist ein Salat:

• Ich würde sogar erwägen, mir Signifier and Signified in mein Büro zu hängen, in mein Wohnzimmer eher jenes. Besonders kurios sind (unter anderem) das, das, das und ganz besonders das.
• Pikachu-, und Mario-Bizarritäten. Und Pac Man. Weh.
• Zweifacher Informatik-Missbrauch beim Werbeblog BoringBoring: Cory Doctorow verwendet den Begriff Halteproblem falsch, und ein anonymer Kommentator ist sich sicher, dass jede formale Beschreibung von Moral unter anderem eine Spezifizierung der natürlichen Zahlen enthält, denn:

  Kurt Godel’s work implies that it is impossible to accurately describe in useful language when it is moral to intervene and when it isn’t; this implies that it is impossible to frame a law that will cover all situations[..]

  Aba sicha doch. Gerüchten zufolge warten führende Internet-Futurologen auf den Tag, an denen ihnen jemand ein Python-Skript schreibt, das Doctorow komplett ersetzt. Sie wissen nicht, wann das passieren wird, aber die Wartezeit vergeht immer schneller (Singulolität!). Ach, wo wir gerade dabei sind, BoringBoring hat übrigens eines der webweit dämlichsten Moderationskonzepte.
• Der Wikipedia-Eintrag zu Verlobungsringen besteht rund zur Hälfte aus einer Abhandlung darüber, ob man die Dinger im Falle einer Entlobung zurückgeben muss oder nicht.
• Abschließend: Falls ich auswandern sollte, dann läge ich im Trend, ich sollte mich aber bald für ein Land entscheiden und nicht durch die Welt erdősen, sonst wird es kompliziert. Übrigens ist meines Wissens nach Ungarisch die einzige Sprache, die den Buchstaben Ő verwendet, dennoch gibt es dazu keinen Eintrag bei hu.wikipedia.org — mehr?

Einst, als bekiffte Hippies ‘Freie Liebe, freie Karten’ bölkend und mit Blumen um den ungewaschenen Hals der Nächstenliebe trunken die ersten 2o Auflagen dieses Sondermüllquartets gratis unters Volk warfen¹ spielte auch ich Magic: the Gathering; daher kann ich nicht darauf verzichten mich — es Holger gleich tuend — an den folgenden albernen Test zu wagen:

Take the Magic: The Gathering ‘What Color Are You?’ Quiz.

¹ Hier zitiere ich (ganz schamlos) die Katz. Was ich mir alles merke…

Wissenschaft. Es arbeitet, Hündinnen.

Und, außerdem, dieses hier. Gar nicht mal so schlecht für eine Seite, die den Hai übersprungen hat, oder?

Ach, übrigens, ich hab auch noch was zum Thema Überabzählbarkeit:

Continue reading "Fee! Φ ! Fo! Fum! Ich rieche Nerds!" »

Wir betrachten die Sprachen L₂:={ww|w∈Σ^* } und L₃:={www|w∈Σ^*} über einem beliebigen endlichen Alphabet Σ mit mindestens zwei Buchstaben. Es ist allgemein bekannt (und anhand von Bar-Hillels Lemma leicht zu zeigen), dass keine dieser Sprachen kontextfrei ist — aber gilt das auch für ihre Komplemente?

Die meisten Leute, die bis hierher mitgelesen haben und die Aufgabe noch nicht kennen, raten wahrscheinlich, dass zumindest bei L₃ auch das Komplement nicht kontextfrei ist, versuchen ihr Glück mit dem Lemma von Bar-Hillel oder gar Ogdens Lemma und ärgern sich nach einiger Zeit sehr, denn diese Ansätze scheitern zwangsläufig. Nicht etwa, weil wir hier einen dieser fiesen Fälle haben, in denen schlimmere Sätze als Ogdens Lemma notwendig sind, sondern weil beide Komplemente kontextfreie Sprachen sind.

Eine Grammatik oder eine Automaten für das Komplement von L₂ anzugeben ist eine beliebte und verhältnismäßig einfache Übungsaufgabe, die sich wunderbar zum Aufwärmen für das Komplement von L₃ eignet. Das nämlich fällt fast allen deutlich schwerer, auch wenn man nur eine kleine Idee haben muss.

Viel Spaß damit.

Einer der eher lästigen Teile des Wissenschaftlerdaseins ist das Warten auf Zeitschriftengutachten zu eingereichten Artikeln; da dort meist keine festen Fristen bestehen kann sich der Prozess schon einmal über Jahre hinziehen¹, und am Ende hat mindestens einer der Gutachter rein gar nichts verstanden und mäkelt ignorant herum².

Andere sind da wohl weit besser dran, wie zum Beispiel ein Herr El Naschie, der Chefredakteur des beim zwar durch und durch bösen, aber doch respektieren und unvermeidbaren Verlag Elsevier erscheinenden Physik-Journals Chaos, Solitons & Fractals ist, und in eben dieser Zeitschrift stolze 322 Artikel veröffentlicht haben soll.

Details dazu und eine kuriose Diskussion finden sich in jenem enthüllenden Eintrag (via); unter den Diskutanten ist übrigens auch Greg Egan. Außerdem entdeckte ich dort einen Link zu einem ausführlichen Verriss eines in eben diesem Journal erschienenen kreationistischen Missbrauch Gödels (wir kennen sowas ja schon). Scheint ein echtes Spitzenjournal zu sein. Zu schade, dass bei einer halbwegs normalen Karriere in meinem Gebiet kein Weg an Elsevier vorbeiführt, denn leider gehören denen auch viele richtige wissenschaftliche Zeitschriften, leider auch so manche richtig wichtige.

¹ Einer unserer beiden noch nicht verzeitschrifteten Artikel wartet zum Beispiel seit Februar auf Gutachten. Allerdings wundert mich das nicht, denn die Beweise sind trotz all unserer erklärenden Bemühungen immer noch nicht gerade angenehm zu lesen, so dass ich eine allzu schnell Begutachtung durchaus bedenklich fände.

² Der Mathematiker Doron Zeilberger hat eine übrigens recht unkonventionelle Meinung zu dieser Angelegenheit.