Verdoppeln

Eine Zahl verdoppeln

Auf dem Band steht eine Zahl n im Unärsystem. Die Maschine soll 2n auf das Band schreiben. Dafür gibt es zwei verschiedene Strategien.

  • Variante 1 (mit Verschiebung): Die alten Einsen werden entfernt und links neben der Eingabe doppelt wiederhergestellt. Am Ergebnis fällt die Verschiebung nicht auf, weil das Band unendlich ist.
  • Variante 2 (in place): Die alten Einsen bleiben, die neuen kommen direkt daneben. Dafür braucht die Maschine einen Trick.
doppelt (Variante 1)
Aufgabe 1 (Variante 1): Erstelle eine Maschine doppelt, die jede alte 1 löscht und dafür links neben der Eingabe zwei neue Einsen schreibt. Zwischen den alten und den neuen Einsen muss dabei immer ein Blank stehen. Am Ende steht 2n auf dem Band.

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

Variante 2: Zeichen als Merkhilfe

Merke: Markieren

Die Maschine darf Zeichen auf dem Band umschreiben, um sich etwas zu merken. Sie ersetzt eine 1 vorübergehend durch eine 0 und kann so bearbeitete von noch unbearbeiteten Einsen unterscheiden. Am Ende schreibt sie die Markierungen wieder in die gewünschten Zeichen um.

Für das Verdoppeln in place gilt: In jeder Runde wird die rechteste 1 zu einer 0, und am linken Rand kommt eine neue 0 hinzu. Sind alle Einsen verbraucht, werden alle Nullen wieder zu Einsen.

Lückentext
Auf dem Band stehen drei Einsen: 111. Nach der ersten Runde steht dort , nach der zweiten Runde .
doppelt (Variante 2)
Aufgabe 2 (Variante 2): Erstelle eine Maschine, die n Einsen in place verdoppelt. Benutze die Strategie von oben und schreibe am Ende alle Nullen wieder in Einsen um.

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 →
← Vorheriger Abschnitt Nächster Abschnitt →