Weltverbesserung

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.

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.

Neben dem Präsidenten standen auch diverse andere Dinge zur Wahl, in Kalifornien z.B. die berüchtigte und massiv propagandistisch unterstützte Proposition 8; ein Verfassungszusatz, der Ehen als ausschließlich ungleichgeschlechtlich definiert und anscheinend angenommen wurde.

Wer gelegentlich einigermaßen politische Blogs oder auch nur die Nachrichten “von drüben” verfolgt weiß das natürlich längst und interessiert sich vielleicht für jenen Artikel über den Sponsor Ahmanson – Millionenerbe, religiöser Fanatiker, Hauptsponsor der religiösen Rechten (samt Kreationisten). Nun ist der Artikel gewiss nicht neutral geschrieben, aber: “My goal is the total integration of biblical law into our lives”, woah.

Außerdem hat er Tourette-Syndrom, was dem ganze nahezu doktorseltsameske Dimensionen verleiht.

Einerseits finde ich es natürlich prinzipiell positiv, wenn jemand seine Millionen einsetzt die Gesellschaft nach seinen Wünschen zu formen, wohl aber wäre es mir wesentlich willkommener, wenn diese Wünsche weit weniger wahnsinnig wären.