Turing machine schoolwork 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&lt;Transition&gt; pT;
    ArrayList&lt;Character&gt; chars = new ArrayList&lt;&gt;();
    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&lt;&gt;();
        for (Transition t : transitions) {
            if (t.getFromState().equals(currentState)) {
                pT.add(t);
            }
        }

        for (int j = 0; j &lt; pT.size(); j++) {
            if (tape.getCells().get(i) == pT.get(j).getInputSymbol()) {
                if (pT.get(j).getWriteSymbol() != EMPTY_SYMBOL) {
                    ArrayList&lt;Character&gt; 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&lt;&gt;();
    for (Transition t : transitions) {
        if (t.getFromState().equals(currentState)) {
            pT.add(t);
        }
    }

    for (int k = 0; k &lt; 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);
}
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 &lt;=, 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&lt;Character&gt; chars = new ArrayList&lt;&gt;();
    final Set&lt;Character&gt; 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 &lt; 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&lt;Transition&gt; possibleTransitions(final String state) {
    final List&lt;Transition&gt; possibleTransitions = new ArrayList&lt;&gt;();
    for (final Transition transition : transitions) {
        if (transition.getFromState().equals(state)) {
            possibleTransitions.add(transition);
        }
    }
    return possibleTransitions;
}