1. Turing-Maschine

Eine Turing-Maschine ist ein mathematisches Modell eines universellen Computers, eingeführt von Alan Turing 1936 in „On Computable Numbers, with an Application to the Entscheidungsproblem". Sie besteht aus einem endlichen Zustands­automaten, einem potentiell unendlichen, in Zellen unterteilten Band, und einem Lese-/Schreibkopf.

Turing, A. M. (1936). On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42, 230–265. cs.virginia.edu

2. Universelle Turing-Maschine

Turings zweites, tieferes Resultat: eine einzelne Maschine U kann jede andere Turing-Maschine M simulieren, indem das Programm von M auf U's eigenes Band geschrieben wird. Damit ist die Church-Turing-These ausgesprochen: alles physikalisch Berechenbare ist berechenbar.

Church, A. (1936). An Unsolvable Problem of Elementary Number Theory. American Journal of Mathematics 58, 345–363. jstor.org

3. Hyperbolische Geometrie & die Poincaré-Scheibe

Wir rendern die Übergänge in der Poincaré-Scheibe, dem konformen Modell der hyperbolischen Ebene: Punkte im Einheitskreis erfüllen die Möbius-Transformation T_a(z) = (z + a) / (1 + a̅ z) als Isometrie.

Poincaré, H. (1882). Théorie des groupes fuchsiens. Acta Math. 1, 1–62. archive.org

4. Warum faltet sich die Berechnung in die Scheibe?

Jeder Turing-Schritt bewegt den Kopf nach links oder rechts. Die Folge dieser Bewegungen entlang des Bandes faltet sich durch wiederholte Anwendung der Möbius-Transformation rekursiv in die Scheibe — die fraktale Selbstähnlichkeit entsteht durch die diskrete Gruppe, die von der Übergangs­regel erzeugt wird.

Milnor, J. (1999). Dynamics in One Complex Variable. Vieweg+Teubner. Kap. 1–2 (Möbius-Gruppen). arxiv.org/abs/math/9201272

5. Busy Beaver

Die Busy-Beaver-Funktion BB(n), eingeführt von Tibor Radó 1962, gibt die maximale Anzahl Einsen an, die eine n-zuständige Turing-Maschine auf einem leeren Band vor dem Halten schreiben kann. Sie wächst schneller als jede berechenbare Funktion — ein direkter Beweis der Unberechenbarkeit.

Radó, T. (1962). On Non-Computable Functions. Bell System Technical Journal 41, 877–884. archive.org
Marxen, H. & Buntrock, J. (1989). Attacking the Busy Beaver 5. drb.insel.de

6. Die Halte-Problematik

Ob eine gegebene Turing-Maschine auf einer gegebenen Eingabe jemals hält, ist unentscheidbar (Turing 1936). In dieser Visualisierung helfen Geschwindigkeits- und Tiefen­regler, lange oder nicht haltende Programme zu erkunden — und mit „Reset" jederzeit zurückzusetzen.