Programme entwerfen: Schleifen und Verzweigungen – Berechenbarkeit und ihre Grenzen

Programme entwerfen

Programme von Hand auszuführen ist der leichtere Teil. Schwieriger ist der Entwurf: Zu einer Aufgabe soll eine Maschine entstehen. Dabei helfen zwei Grundmuster.

Merke: Schleife

Bewegt sich der Kopf durchgehend in dieselbe Richtung über den Bandinhalt, ohne die Richtung zu wechseln, bleibt die Maschine im gleichen Zustand. Das ist eine Wiederholung (Schleife).

Merke: Verzweigung

Muss der Kopf die Richtung ändern, wechselt die Maschine in einen neuen Zustand. Das ist eine Verzweigung.

Vor dem Entwerfen lohnt sich ein Blick auf Anfangs- und Endzustand: Wo steht der Kopf zu Beginn, wo soll er am Ende stehen, und welche Zeichen kann er auf seinem Weg lesen?

Eine Tabelle muss nicht vollständig sein: Für ein Zeichen ohne Regel hält die Maschine an. Das darf man bewusst nutzen.

Aufgabe 1

Aufgabe 1: Auf dem Band steht eine beliebig lange Folge von Einsen. Der Kopf soll sich über die Folge bis links daneben bewegen und dabei jede 1 durch eine 0 ersetzen. Dort soll die Maschine halten. Der Kopf muss am Ende nicht rechts stehen.

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

Aufgabe 2

Aufgabe 2: Auf dem Band steht eine beliebige Folge aus 0 und 1. Der Kopf soll nach links bis neben die Folge laufen und dabei jedes Zeichen invertieren (aus 0 wird 1, aus 1 wird 0). Dort soll die Maschine halten.

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

Aufgabe 3

Aufgabe 3: Auf dem Band steht eine beliebige Folge aus 0 und 1. Die Maschine soll von rechts die erste 1 suchen, sie durch eine 0 ersetzen und wieder an den rechten Rand zurückkehren. Dort soll sie halten. Steht keine 1 auf dem Band, bleibt es unverändert.

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

Aufgabe 4

Aufgabe 4: Das Zustandsdiagramm zeigt eine Maschine. Übertrage es in die Transitionstabelle und teste die Maschine. Beschreibe danach in der Aufgabe darunter, was sie tut.

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

Freitext

Beschreibe, was die Maschine aus Aufgabe 4 tut. Welche Rolle hat jeder der beiden Zustände?

💡 Zum Speichern deiner Antwort bitte einloggen.

✏️ Übungen zu diesem Kapitel

5 freiwillige Aufgaben zum Üben und Weiterdenken.

Zu den Übungen →