Universal Turing Machine

The more I practice, the more I explore extreme situations. I have tried to go faster. Other times I Programmed with Nothing. Maybe it is the difficulty of only using low level constructs that makes these group of coding constraints appealing to me - which makes coding in assembly still interesting to some people, too. Then I tried to create Fizz Buzz using a Turing machine. I guess I lacked the purity of Computer Science university exercises. I will dive into Turing machines from a practical coding perspective using Java here.

Turing Machine
What is a Turing machine (TM)? First the TM is a though experiment. It was not meant to be practical. It is "the thing with the tape where a read-write head is able to read a zero or a one, write a zero or a one, erase the value, and move left or right." It is supposed to be Turing complete, which means it is equivalent to all programming languages today. That was my understanding of a TM when I started. But that understanding was impractical. Is a TM a program or a set of programs or a programming language? How can it be a specific program and Turing complete at the same time? And how could I implement anything like that?

Basic (Java) Building Blocks
First I need the building blocks. There is a set of symbols, maybe only 0 or 1 (a bit) or maybe a character to make things easier. So an empty marker interface Symbol should do. (The interface is optional, I like to make the symbol different from plain Object. I could use a plain char as well.) Then there is the tape which can be read and written to. The Tape class represents the tape as a data structure, such as an array or a list. Each cell of the tape holds a symbol.

class Tape<SYM extends Symbol> {

  private Map<Integer, SYM> cells = new TreeMap<>();
  private SYM defaultSymbol;
  private int headPosition = 0;

  Tape(List<SYM> symbols, SYM defaultValue) {
    for (int i = 0; i < symbols.size(); i++) {
      this.cells.put(i, symbols.get(i));
    }
    this.defaultSymbol = defaultValue;
  }

  SYM read() {
    return cells.getOrDefault(headPosition, defaultSymbol);
  }

  void write(SYM symbol) {
    cells.put(headPosition, symbol);
  }

  void moveHead(Direction direction) {
    switch (direction) {
    case LEFT:
      headPosition--;
      break;
    case NONE:
      break;
    case RIGHT:
      headPosition++;
      break;
    default:
      throw new IllegalArgumentException(direction.name());
    }
  }
}

The tape could be infinite, and I chose a Map for each symbol by its position. The default symbol is used for tape positions that have not been written to. The constructor accepts the initial content of the tape as the starting state of the machine. Now to the Turing machine:

class TuringMachine<SYM extends Symbol> {

  private Tape<SYM> tape;
  private State state;

  TuringMachine(Tape<SYM> tape, State initialState) {
    this.tape = tape;
    this.state = initialState;
  }

  private void setState(State state) {
    this.state = state;
  }

  private SYM read() {
    return tape.read();
  }

  private void write(SYM symbol) {
    tape.write(symbol);
  }

  private void move(Direction direction) {
    tape.moveHead(direction);
  }

  void loop() {
    while (!state.isTerminal()) {
      act();
    }
  }

  // ...

Following the description of a Turing machine, it has a state which can change. It can read the symbol currently present on the tape at the position of its read/write head. It can write a new symbol on the tape at the position of its read/write head, replacing the symbol that was previously there. And it can move its read/write head one position to the left or right along the tape. The machine runs as long as its state is not final. In each step (method act shown below) the machine reads the symbol present in the tape's cell, and based on the current state and the read symbol, it determines the next state and the symbol to write on the tape, then it moves the head left or right by one cell.

class TuringMachine<SYM extends Symbol> {

  // ...

  private void act() {
    SYM symbol = read();

    // transition to nextState determines
    // symbolToWrite and directionToMove

    setState(nextState);
    write(symbolToWrite);
    move(directionToMove);
  }

}

Of course this was not my initial code. I reached it by refactoring, cleaning up and structuring the code again and again. If this is a Turing machine, where is the actual program? The Tape and TuringMachine classes form a Universal Turing Machine (UTM). The UTM can simulate the behaviour of any Turing machine. It takes the description of any arbitrary Turing machine as input and mimics its operation on a given input string. Aha! My infrastructure can run an arbitrary Turing machine which makes each TM an individual program and the UTM the interpreter. Maybe I should have read the whole article on Wikipedia first.

State Transitions
The actual program of a Turing machine is the set of its states and possible state transitions. It is a state machine, i.e. a graph of state nodes, and each edge between two states contains additional data: The Symbol symbolToWrite and the Direction directionToMove. In text, the easiest way to define this state machine is with a transition table of State state, Symbol symbol, State newState, Symbol newSymbol, Direction direction which is a TransitionTableRow in my TransitionTable implementation. (The whole transition logic is too much code to show here, the working solution is on my GitHub.) As I will create many transitions, I add defaults to the tables, e.g. state == null applies to all states, symbol == null applies to all symbols and newState == null or newSymbol == null does not change the current state or symbol. I want to avoid defining more table rows than strictly necessary.

A Simple Example
Now is the perfect time for an example. We want to set all bits of a binary number, e.g. 011010. The symbols are the bits 0 and 1 and a marker for the end of the input,

enum Bit implements Symbol {
  _0, _1, END_OF_TAPE
}

Starting at the left-most / highest bit. The transitions are

• If the machine is running and the current bit is 0, then keep running, write a 1 and move right.
• If the machine is running and the current bit is 1, then keep running, write a 1 and move right.
• If the machine is running and the input has ended, then stop running (halt).

This is a simple machine and there are only two states: running and stopped,

enum S implements State {
  RUNNING, HALT;

  @Override
  public boolean isTerminal() { return this == HALT; }
}

and the whole things runs in this test,

class SimpleExampleTest {

  @Test
  void replaces0With1() {
    S initialState = S.RUNNING;
    var _011010 = Arrays.asList(_0, _1, _1, _0, _1, _0, END_OF_TAPE);
    var tape = new Tape<>(_011010, END_OF_TAPE);

    TransitionTable transitions = new TransitionTable().
        row(S.RUNNING, _0, null, _1, Direction.RIGHT).
        row(S.RUNNING, _1, null, null, Direction.RIGHT).
        row(S.RUNNING, END_OF_TAPE, S.HALT, null, Direction.NONE);

    var machine = new TuringMachine<>(tape, transitions, initialState);

    machine.loop();

    var expected_111111 = Arrays.asList(_1, _1, _1, _1, _1, _1, END_OF_TAPE);
    var actualResult = tape.getCells();
    assertEquals(expected_111111, actualResult);
  }
}

Now I know what a Turing machine is and how it is supposed to work. Using the Constructive Approach I created an UTM (TuringMachine.java) and an instance of a TM (in SimpleExampleTest.java). Now I can play around and see what is possible using only state transitions... I encourage you to do the same, clone my fizzbuzz-turing-machine repository and play around with the code in the universal package. This concludes the first part - the foundation if you like - of me implementing Fizz Buzz using a Turing machine.