Turing-Maschine mit Redstone in Minecraft

Eine Turing-Maschine mit Redstone in Minecraft bauen

Eine Turing-Maschine besteht aus einem unendlichen, in Zellen unterteilten Band, einem Lese-/Schreibkopf und einer Übergangstabelle, die als Programm dient. In Minecraft werden diese Komponenten mit Redstone simuliert – einem Signalübertragungssystem mit 16 Leistungsstufen (0 bis 15). Redstone-Staub leitet ein Signal bis zu 15 Blöcke weit, wobei die Signalstärke pro Block um eine Stufe abnimmt.

Wichtige Redstone-Bauteile:

• Redstone-Torch: Invertiert das Signal (NICHT-Gatter).
• Hebel: Liefert eine stabile, konstante Stromquelle.
• Knopf: Erzeugt einen Impuls fester Dauer.
• Redstone-Verstärker: Erhöht die Signalstärke, erzwingt die Einwegleitung und fügt eine Verzögerung von 1–4 Ticks hinzu.
• Komparator: Vergleicht oder subtrahiert Signalstärken.

Diese Bauteile lassen sich zu logischen Gattern kombinieren: NICHT (Torch), UND (zwei Verstärker speisen eine Torch), ODER (zusammenlaufende Leitungen) sowie NAND/NOR (verschiedene Kombinationen). Die Maschine arbeitet mit einem 4-Zeichen-Alphabet: 0, 1, leer (ε) und ein reservierter Zustand.

Speicherzelle des Bandes

Jede Zelle speichert 4 Bit (Werte 0–15) und gibt ihr Signal nach Aktivierung kontinuierlich aus. Beispielsweise könnte eine Zelle 0101 halten. Ein Knopf auf der linken Seite setzt die Zelle zurück. Die zusätzlichen Bits bieten Spielraum für zukünftige Erweiterungen.

Das vollständige Band besteht aus 8 solcher Zellen, was insgesamt 32 Bit Speicher ergibt.

Schieberegister für den Kopf

Dieses Register verfolgt die Position des Lese-/Schreibkopfs auf dem Band. Eine leuchtende Lampe zeigt die aktuell aktive Zelle an. Knöpfe auf der rechten Seite steuern die Bewegung: links, rechts und Reset (der den Kopf zur linken Lampe zurücksetzt). Eine optionale Lampe ganz links signalisiert den Abschluss eines Verschiebevorgangs und hilft, Zeitverzögerungen im Ausführungszyklus zu minimieren.

Das Register verarbeitet Bitverschiebungen, um den Kopf über das Band zu bewegen.

Programmspeicherzelle

Jede Programmspeicherzelle enthält 10 Bit an Befehlsdaten:

• 4 Bit für den zu schreibenden Wert.
• 2 Bit für die Kopfverschiebung (10 = nach links, 01 = nach rechts).
• 4 Bit für den nächsten Maschinenstatus.

Die Operationen folgen einer strengen Abfolge: Schreiben → Verschieben → Statusübergang. Das vollständige Programm nutzt 20 Zellen und deckt 4 Zustände × 4 Symbole (einschließlich ε und des Haltezustands) ab.

Binär-Dezimal-Wandler

Dieses Modul übersetzt Binäradressen ins Dezimalsystem, um die Bandzellen korrekt anzusteuern. Die Eingabe erfolgt von rechts (z. B. wird die Binärzahl 10 links als Dezimalzahl 2 ausgegeben). Dies vereinfacht die Speicheradressierung.

Ausführungszyklus

Feste Zeitverzögerungen (2 Sekunden pro Operation) halten alles synchronisiert, ohne explizite Fertigstellungssignale zu benötigen:

• Symbol aus der aktuellen Bandzelle lesen.
• Übergangsregel basierend auf aktuellem Zustand und Symbol nachschlagen.
• Neuen Wert aus der Übergangstabelle schreiben.
• Kopf nach links oder rechts verschieben.
• Zum nächsten Maschinenstatus wechseln.
• Wird der Haltezustand erreicht, stoppen; andernfalls Zyklus wiederholen.

Ein orangefarbenes Kabel führt vom Programmmodul zur Ausführungsschleife, um das Haltesignal zu übertragen.

Gesamtarchitektur

Der vollständige Aufbau integriert:

• 20 Programmbefehlszellen.
• 8 Bandspeicherzellen.
• Das Schieberegister für den Kopf.
• Den synchronisierten Ausführungszyklus.
• Binär-Dezimal-Adresswandler.

Als praktischer Beweis kann die Maschine erfolgreich eine auf dem Band gespeicherte Zahl inkrementieren.

Wichtige Erkenntnisse

• Redstone simuliert die Logik einer Turing-Maschine präzise mit Standardgattern und Signalstärken von 0–15.
• 4-Bit-Speicherzellen verfügen über integrierte Redundanz für eine einfachere Skalierung.
• Feste Zeitverzögerungen optimieren die Ausführungsschleife, indem sie auf Rückkopplungssignale verzichten.
• Ein 4-Zeichen-Alphabet und 4 interne Zustände ergeben 20 mögliche Übergänge.
• Der Aufbau ist für spezifische Anwendungsfälle, wie die Binär-Inkrementierung, voll funktionsfähig.

— Editorial Team