Turing machine schoolwork

Question

Our teacher doesn't give much feedback on our code itself. Was just looking for some feedback on how I could improve on this. This is the method that tests the string against the Turing machine that is built from a file.

The entire project is on GitHub.

public boolean run(String input) {
    String currentState = startState;
    ArrayList<Transition> pT;
    ArrayList<Character> chars = new ArrayList<>();
    int i = 0;

    for (char c : input.toCharArray()) {
        if (!inputAlphabet().contains(c)) {
            return false;
        } else {
            chars.add(c);
        }
    }
    tape.setCells(chars);
    tape.setHeadPosition(i);
    System.out.println(currentState);

    while (i != tape.getCells().size()) {
        pT = new ArrayList<>();
        for (Transition t : transitions) {
            if (t.getFromState().equals(currentState)) {
                pT.add(t);
            }
        }

        for (int j = 0; j < pT.size(); j++) {
            if (tape.getCells().get(i) == pT.get(j).getInputSymbol()) {
                if (pT.get(j).getWriteSymbol() != EMPTY_SYMBOL) {
                    ArrayList<Character> temp;
                    temp = tape.getCells();
                    temp.set(i, pT.get(j).getWriteSymbol());

                    tape.setCells(temp);
                }

                if (pT.get(j).getDirection().charAt(0) == DIRECTION_RIGHT) {
                    i++;
                    tape.setHeadPosition(i);
                } else if (pT.get(j).getDirection().charAt(0) == DIRECTION_LEFT) {
                    i--;
                    tape.setHeadPosition(i);
                }
                currentState = pT.get(j).getToState();
                System.out.println(currentState);
                j = pT.size();
            }
        }
        if (rejectStates.contains(currentState)) {
            return false;
        }
    }


    pT = new ArrayList<>();
    for (Transition t : transitions) {
        if (t.getFromState().equals(currentState)) {
            pT.add(t);
        }
    }

    for (int k = 0; k < pT.size(); k++) {
        if (pT.get(k).getInputSymbol() == EMPTY_SYMBOL) {
            currentState = pT.get(k).getToState();
            System.out.println(currentState);
            if (pT.get(k).getDirection().charAt(0) == DIRECTION_RIGHT) {
                i++;
                tape.setHeadPosition(i);
            } else if (pT.get(k).getDirection().charAt(0) == DIRECTION_LEFT) {
                i--;
                tape.setHeadPosition(i);
            }
            k = pT.size();
        }
    }

    return acceptStates.contains(currentState);
}

Answer 1

Some grist for the mill:

When variables will not be reassigned, it's helpful to declare them as final to reduce cognitive load on the reader.

When using the Collections API, it's preferable to declare interface types rather than implementations (List instead of ArrayList) unless you need functionality specific to the implementation type.

Declare variables as closely to where they're first used as is possible.

When you return in the if clause, you don't need an else clause.

Calling inputAlphabet().contains() once for every character in the input is very inefficient, especially given that inputAlphabet() is running a loop to create the list. Call inputAlphabet() once and keep a local variable to hold it. And have inputAlphabet() return a Set instead of a List, which gets you contains() at O(1) instead of O(n).

input.toCharArray() is easy to read, which makes it probably correct in this case, but be aware that it's marginally less efficient than using an indexed loop and calling input.charAt(i) because it creates a new char[].

You don't need to keep a Tape instance variable. Just create a new one in run(). It might be nice if the Tape constructor accepted a list of cells.

Probably not relevant, but your code is not thread-safe. It will break if multiple threads call run at the same time.

Don't reuse a variable (pT) for different things in the same method. It makes it hard for the reader to keep track of what it contains.

pT is a poor variable name. I think it means possibleTransitions? Variables should clearly indicate what they're referencing. Another example is t instead of transition.

The loop building the transitions could be extracted into a method.

It's traditional in looping constructs to check <=, instead of != to avoid a possible infinite loop if a bug puts you past the exact value you want to terminate on.

You can localize i and use a for loop, because you know is has to be tape.getCells().size() when you're done looping.

Your code might be easier to read with a guard clause if (.. != .. ) { continue; rather than nesting.

Rather than setting the value of j to break the loop, just use break. Then you can use an enhanced for loop rather than indexing on j.

Your temp dancing is not meaningful. Since Tape is returning an unsafe copy from getCells(), you could just do tape.getCells().set(i, ..). Even better would be changing the API of Tape to have the methods to access the cells (tape.getCellAt(int), tape.setCellAt(int, Character) instead of returning the array for you to mess around with. While you're at it, add a method like size() or length() to tape and get rid of getCells altogether. Let Tape hide the fact that it's using a List under the covers, and you can change the implementation later without breaking other code.

It's unclear why a Transition's direction and the current state are treated as Strings when they're only ever one character long.

It also be nice if Transition could be changed so you could do something like i = possibleTransition.applyDirection(i), and the Transition determines whether to add one, subtract one, or do nothing. Then that if .. else if .. block reduces to i = possibleTransition.applyDirection(i); tape.setHeadPosition(i);

Your second for loop with the k index has the same break; issue as the first. You can again use the enhanced for loop.

It's unclear what this loop is doing with Tape, since you're making changes that effectively vanish once the method exists. It looks like that code can just go. In fact, since getHeadPosition is never called in your codebase, I'm not sure why you're tracking it at all.

If you were to make all of these modifications, your code might look something like the code below. This is untested, so I might very well have broken something.

public boolean run(final String input) {
    final List<Character> chars = new ArrayList<>();
    final Set<Character> inputAlphabet = inputAlphabet();
    for (final char c : input.toCharArray()) {
        if (!inputAlphabet.contains(c)) {
            return false;
        }
        chars.add(c);
    }

    String currentState = startState;

    final Tape tape = new Tape(chars);
    for (int i = 0; i < tape.size(); i++) {

        for (final Transition transition : this.possibleTransitions(currentState)) {
            if (tape.getCellAt(i) != transition.getInputSymbol()) {
                continue;
            }

            if (transition.getWriteSymbol() != EMPTY_SYMBOL) {
                tape.setCellAt(i, transition.getWriteSymbol());
            }

            i = transition.applyDirection(i);
            currentState = transition.getToState();
            break;
        }

        if (this.rejectStates.contains(currentState)) {
            return false;
        }
    }

    for (final Transition transition : possibleTransitions(currentState)) {
        if (transition.getInputSymbol() == EMPTY_SYMBOL) {
            currentState = transition.getToState();
            break;
        }
    }
    return acceptStates.contains(currentState);
}

private List<Transition> possibleTransitions(final String state) {
    final List<Transition> possibleTransitions = new ArrayList<>();
    for (final Transition transition : transitions) {
        if (transition.getFromState().equals(state)) {
            possibleTransitions.add(transition);
        }
    }
    return possibleTransitions;
}

Answer 2

I agree with Eric Stein that your Tape class as written doesn't provide a useful abstraction. I see two possible ways to fix it:

• One option would be to get rid of the class entirely, and just use a List<Character> to represent the tape and an int to represent the head position in the TuringMachine class. The Java List interface is already a perfectly reasonable representation of an extensible one-dimensional sequence of values, so you can just program to it instead of defining your own.

• Alternatively, if you'd rather keep the Tape class, you should remove the getCells() method (since it needlessly exposes the internals of the class) and just provide methods to access the values on the tape directly.

In fact, you don't even need to allow access to values at arbitrary positions, since a Turing machine tape, by definition, only allows reading and writing to the cell at the current position of the head. So the only methods you really need are something like:

• public char read(): return the value of the cell at the current head position;
• public void write(char value): set the value of the cell at the current head position;
• public void moveHead(int steps): move the head by steps positions;

and a constructor that accepts a CharSequence and/or a char[] parameter to initialize the content of the tape. (You may also want to provide a toString() method for easier debugging.)

One advantage of going this way is that you can later optimize the internal implementation of the tape without having to change any code that uses it. For example, one simple optimization might be to use a StringBuffer instead of an ArrayList<Character> to store the contents of the tape, which should be more efficient. Also, letting the tape extend in both directions could be easily and efficiently implemented by using two StringBuffers (or ArrayLists) internally.

---

Also, the way you're representing the state machine itself is quite inefficient: at every step, you're looping over all the possible state transitions to find the matching one.

A more efficient method would be to store the state transitions in a Map (implemented e.g. as a HashMap — but you should usually just program to the interface whenever possible) to let you look them up efficiently. Since you need to look up the transitions using a combination of two keys (the current state and the character on the tape), you have two options: either use a nested Map<String, Map<Character, Transition>> or define a wrapper class to store a (state, input) pair, with a suitable hashCode() method, and use it as the key to a single map.

However, arguably an even more elegant solution would be to introduce a State class that stores all the properties of a single state in your state machine, including both whether or not it's an accepting state and all the possible transitions from that state. Also, the State class should not expose its internal implementation of the transition map (which should probably be something like a HashMap<Character, Transition>), but rather should simply provide a method like:

public Transition getTransition(char tapeValue)

Also, you should explicitly define and document the behavior of this method in the case where no matching transition is found (which in most standard definitions of a Turing machine indicates that the machine halts). Reasonable behaviors might be either returning null or throwing a specific custom exception, but either way, this should be documented. If you wanted to get fancy with wrapper objects, you could even make the method return an Optional<Transition>, although I don't personally see any real added value in that for this particular use case.

I would also make the Transition class store direct references to its source and target State objects instead of string labels, and have getFromState() and getToState() return the states directly. Note that you'd still need to maintain a string-to-state-object map while building the state machine, but you no longer need it after all the states and transitions have been built.

(Also, if you wanted, you could make the State and Transition objects immutable, since there's no need to change them after the state machine has been built. Unfortunately, writing a proper builder class for an immutable state machine would be a somewhat nontrivial exercise all by itself, due to the possibility of circular state transition chains, so just leaving the classes mutable might be easier in practice.)

---

Finally, I should note that the way your "Turing machine" works seems kind of unusual. While there are several different (but essentially equivalent) ways of defining a Turing machine, yours doesn't really seem to match any of them.

Basically, as far as I can tell, your machine uses a finite-length tape (whereas most definitions of a Turing machine allow the tape to extend infinitely in one or both directions) and runs until either:

1. it reaches one of the states defined as "rejecting" (in which case the input is immediately rejected),
2. it walks off the right-hand end of the tape (in which case it runs one more step, reading an EMPTY_SYMBOL off the end of the tape, and then uncoditionally halts, accepting the input if the current state is defined as "accepting" and rejecting it otherwise), or
3. it walks off the left-hand side of the tape (in which case it crashes with an IndexOutOfBoundsException, since you don't have any code to handle that case).

Basically, what you have looks like some kind of a weird hybrid of a Turing machine and a classical finite state machine that reads its input strictly sequentially. Due to the lack of an infinite tape, its computational power is strictly weaker than that of a proper Turing machine (and in fact theoretically equivalent to that of a finite state machine, although in practice your machine can have much more complex behavior than a simple FSM with the same number of states could). If that's not how you intended it to work, then your code would appear to be buggy.