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.