Lernpfad:Lerntheke Marsrover/31

Fleißige Rover

Erklärung Turing Maschine / Busy Beaver.

Der Rover kann eine Turingsmaschine simulieren, aber natürlich nicht mit unendlich viel Speicherplatz. Das Band kann maximal 15 Zeichen breit sein.

Wir legen folgende Bedingungen für die Rover-Turingmaschine fest:

Der Rover ist der Lese-/Schreibkopf und steht mit Blickrichtung nach oben.
Der Rover kann sich nur ein Feld nach links oder rechts bewegen.
Ein leeres Feld stellt eine 0 dar, ein Feld mit einer Marke eine 1.
Pro Aufruf der act()-Methode kann der Rover das aktuelle Feld auf eine Marke prüfen, die Marke entfernen oder eine setzen und sich ein Feld bewegen. Mehr nicht.

Das Rolle des Bandes unserer Rover-Turingmaschine übernimmt eine Zeile in der Roverwelt. Du kannst die Karte "karte31_fleissige_rover" laden, um die Ausgangssituation zu erhalten.

Arbeitsauftrag

Implementiere die Methoden links() und rechts(), die den Rover ein Feld nach links / rechts bewegen. Der Rover schaut zu Beginn und nach Ablauf nach oben.

Lösung

    public void links() {
        drehe("links");
        fahre();
        drehe("rechts");
    }
    
    public void rechts() {
        drehe("rechts");
        fahre();
        drehe("links");
    }

Damit der Rover sich auch wie der Schreib-/Lesekopf der Turingsmaschine verhalten kann, muss er sich einen Zustand merken können und basierend auf diesem Zustand entscheiden können, wie er weiterarbeitet. Ein Zustand kann einfach durch eine Zahl repräsentiert werden. Wir starten immer in Zustand 0.

In jedem Zustand muss der Rover entschieden was er macht. Diese Entschiedung hängt davon ab, ob auf dem Feld eine Marke liegt, oder nicht. Zur besseren Ünersicht (siehe Strukturierte Zerlegung) schreibst du für jeden Zustand eine eigene Methode, die die passende Aktion ausführt und den neuen Zustand als Zahl zurückgibt.

Für Zustand 0 könnte das zum Beispiel so aussehen:

    public int zustand0() {
        if( markeVorhanden() ) {// es wurde "1" gelesen
            entferneMarke();        // schreibe eine "0"
            links();                // bewege den Kopf nach links
            return 0;               // bleibe in Zustand 0
        } else {                // Es wurde "0" gelesen
            setzeMarke();           // schreibe eine "1"
            rechts();               // bewege den Kopf nach links
            return 1;               // wechsele in Zustand 1
        }
    }

Arbeitsauftrag

Ergänze in Zeile 9 hinter private Display anzeige; diesen Code: private int zustand = 0;
Ergänze innerhalb der Klasse Rover die Methode public int zustand0() von oben.
Implementiere die act()-Methode wie folgt:

    public void act() {
        switch( zustand ) {
            case 0:                     // Wenn in Zustand 0
                zustand = zustand0();   // führe die Methode "zustand0" aus
                break;                  // und beende die act()-Methode
        }
    }

Probiere den Turing-Rover aus und prüfe, was diese "Turingmaschine" macht.

Lösung

Der obere Teil der Klasse Rover muss wie folgt aussehen:

public class Rover extends Actor {

    private Display anzeige;

    private int zustand = 0;
    
    /**
     * Act-Methode des Rovers. Programmiere hier deinen Algorithmus und starte
     * ihn mit dem "Act"-Button in Greenfoot.
     */
    public void act() {
        switch( zustand ) {
            case 0:                     // Wenn in Zustand 0
                zustand = zustand0();   // führe die Methode "zustand0" aus
                break;                  // und beende die act()-Methode
        }
    }
    
    public int zustand0() {
        if( markeVorhanden() ) {// es wurde "1" gelesen
            entferneMarke();        // schreibe eine "0"
            links();                // bewege den Kopf nach links
            return 0;               // bleibe in Zustand 0
        } else {                // Es wurde "0" gelesen
            setzeMarke();           // schreibe eine "1"
            rechts();               // bewege den Kopf nach links
            return 1;               // wechsele in Zustand 1
        }
    }
    
    public void links() {
        drehe("links");
        fahre();
        drehe("rechts");
    }
    
    public void rechts() {
        drehe("rechts");
        fahre();
        drehe("links");
    }
    
    // Rest der Klasse Rover folgt hier ...
    
}

Die Turingmaschine schreibt eine "1" (eine Marke) auf das Band und macht dann nichts mehr (terminiert).