Verschieben, Kopieren, Multiplizieren – Berechenbarkeit und ihre Grenzen

Multiplizieren aus Bausteinen

Die Turingmaschine kann im Unärsystem auch multiplizieren. Dafür entsteht die Maschine in drei Stufen: Aus einer Verschiebemaschine wird eine Kopiermaschine, und aus der Kopiermaschine eine Multiplikationsmaschine.

Merke: Maschinen aus Bausteinen

Eine neue Maschine darf auf einer fertigen aufbauen: Man löst zuerst ein einfacheres Teilproblem, testet die Maschine und erweitert sie dann Schritt für Schritt. So bleibt auch eine große Aufgabe überschaubar.

In diesem Kapitel trennt ein einzelnes Blank die beiden Zahlen, weil die 0 als Markierung gebraucht wird (siehe Kapitel 8). Beide Zahlen sind mindestens 1.

Verschieben

Aufgabe 1 (Verschieben): Links steht eine 0 zur Orientierung, dann Blanks, rechts davon n Einsen, zum Beispiel 0####11 für n = 2. Die Maschine soll die Einsen so verschieben, dass sie unmittelbar links neben dem Feld stehen, das vorher links von der Eingabe lag. Aus 0####11 wird 0#11. Die 0 darf sich nicht ändern. Am Ende steht der Kopf unter der rechtesten 1.

Ohne Anmeldung wird deine Maschine nicht gespeichert. „Maschinen merken“ und „Datei speichern“ funktionieren trotzdem.

Kopieren

Aufgabe 2 (Kopieren): Erweitere die Maschine so, dass die alten Einsen stehen bleiben und nur kopiert werden. Aus n Einsen wird eine Kopie links daneben, getrennt durch ein Blank: aus 111 wird 111#111. Am Ende steht der Kopf unter der rechtesten alten 1.

Ohne Anmeldung wird deine Maschine nicht gespeichert. „Maschinen merken“ und „Datei speichern“ funktionieren trotzdem.

Multiplizieren

Aufgabe 3 (Multiplizieren): Auf dem Band stehen zwei Zahlen n1 und n2 im Unärsystem, getrennt durch ein Blank, zum Beispiel 11#111. Am Ende soll n1 · n2 auf dem Band stehen und der Kopf unter der rechtesten 1.

Ohne Anmeldung wird deine Maschine nicht gespeichert. „Maschinen merken“ und „Datei speichern“ funktionieren trotzdem.

✏️ Übungen zu diesem Kapitel

2 freiwillige Aufgaben zum Üben und Weiterdenken.

Zu den Übungen →