Die Turing-Maschine in Java 9 (JShell) mit Beispielen

tm11000.java

/open turing.java

Transition[] ts = new Transition[] {
    new Transition("s1",'1','0',Move.RIGHT,"s2"),
    new Transition("s1",'0','0',Move.NONE,"HALT"),
    new Transition("s2",'1','1',Move.RIGHT,"s2"),
    new Transition("s2",'0','0',Move.RIGHT,"s3"),
    new Transition("s3",'1','1',Move.RIGHT,"s3"),
    new Transition("s3",'0','1',Move.LEFT,"s4"),
    new Transition("s4",'1','1',Move.LEFT,"s4"),
    new Transition("s4",'0','0',Move.LEFT,"s5"),
    new Transition("s5",'1','1',Move.LEFT,"s5"),
    new Transition("s5",'0','1',Move.RIGHT,"s1")
}

Tape tape = new Tape("11000", '0', 0);

TM tm = new TM();
tm.setTransitions(ts);
tm.setTape(tape);
tm.setState("s1");

tm111-1=.java

/open turing.java

Transition[] ts = new Transition[] {
    new Transition("1",'e','e',Move.RIGHT,"1"),
    new Transition("1",'1','1',Move.RIGHT,"1"),
    new Transition("1",'-','-',Move.RIGHT,"1"),
    new Transition("1",'=','e',Move.LEFT,"2"),
    new Transition("2",'1','=',Move.LEFT,"3"),
    new Transition("2",'-','e',Move.LEFT,"HALT"),
    new Transition("3",'1','1',Move.LEFT,"3"),
    new Transition("3",'-','-',Move.LEFT,"4"),
    new Transition("4",'e','e',Move.LEFT,"4"),
    new Transition("4",'1','e',Move.LEFT,"1")
}

Tape tape = new Tape("111-1=", 'e', 0);

TM tm = new TM();
tm.setTransitions(ts);
tm.setTape(tape);
tm.setState("1");

turing.java

enum Move { LEFT, RIGHT, NONE }

class Tape {
    String symbols;
    char empty;
    int pos;
    Tape(String symbols, char empty, int pos) {
        this.symbols = symbols;
        this.empty = empty;
        this.pos = pos;
    }
    void move(Move m) {
        switch(m) {
            case LEFT:
                if (pos == 0) symbols = empty + symbols;
                else pos--;
                break;
            case RIGHT:
                if (pos == symbols.length()-1) symbols = symbols + empty;
                pos++;
                break;
            default:
                break;
        }
    }
    char read() {
        return symbols.charAt(pos);
    }
    void write(char symbol) {
        symbols = "" + symbols.subSequence(0,pos)
                + symbol 
                + symbols.subSequence(pos+1,symbols.length());
    }
    public String toString() {
        String repr = " " + String.join(" ",symbols.split("")) + " ";
        int p = pos * 2 + 1; // 0,1,2,3,4 ... -> 1,3,5,7,9 ...
        return "" + repr.subSequence(0,p-1) + "<" +
               repr.subSequence(p,p+1) + ">" +
               repr.subSequence(p+2,repr.length()); 
    }
}

class Transition {
    String fromState, toState;
    char read, write;
    Move move;
    Transition(String fromState, char read, char write, Move move, String toState) {
        this.fromState = fromState;
        this.read = read;
        this.write = write;
        this.move = move;
        this.toState = toState;
    }
}

class TM {
    Tape tape;
    Transition[] transitions;
    String state;
    void setTape(Tape tape) {
        this.tape = tape;
    }
    void setTransitions(Transition[] transitions) {
        this.transitions = transitions;
    }
    void setState(String state) {
        this.state = state;
    }
    ArrayList<Transition> findTransitions() {
        char read = tape.read();
        ArrayList<Transition> filteredT = new ArrayList<>();
        for(Transition t : transitions)
            if (t.fromState == state && t.read == read) filteredT.add(t);
        return filteredT;
    }
    boolean step() {
        ArrayList<Transition> foundTransitions = findTransitions();
        if (foundTransitions.size() == 0) return false;
        Transition transition = foundTransitions.get(new Random().nextInt(foundTransitions.size()));
        tape.write(transition.write);
        tape.move(transition.move);
        state = transition.toState;
        return true; 
    }

    void run() {
        int counter = 0;
        System.out.printf("%3d: %s -- %s\n",counter,tape,state);
        while(!state.equals("HALT")) {
            if (!step()) break;
            counter++;
            System.out.printf("%3d: %s -- %s\n",counter,tape,state);
        }
    }
}