4.4.5.1 - Turing machines as a model of computation (Java)

Machine structure and transition rules

A Turing machine is a formal computer with a fixed program controlling a read-write head on a tape, rather than a description of a particular physical processor.

The machine has a finite set of states, a finite tape alphabet including a blank symbol, and an infinite tape divided into squares. Its head senses one square, can replace that square's symbol and moves one square left or right according to a rule. There is a designated start state. States with no outgoing transitions are halting states. AQA exam machines use one tape infinite in one direction: here cell 0 is its left boundary and cells extend without limit to the right. A rule must not move left from cell 0 in this example.

Define the transition function by

where q is the current state, s the symbol read, q′ the next state, s′ the symbol written and D the move L or R. Some texts order the outputs differently; use the convention supplied in the task. For a machine that appends one unary mark to a consecutive string of 1s:

The alphabet is $\{1,\square\}$, the states are $\{q_{\mathrm{Scan}},q_H\}$, and qH has no outgoing transitions. A diagram expresses the same fixed program: an arrow's start/end states give q/q′ and its label gives the read symbol, write symbol and movement.

[DIAGRAM: asset_slug: turing-append; description: A start state qScan loops on 1/1,R and enters halting qH on blank/1,R; a tape beginning at cell0 contains 111 followed by blanks, with the initial head at cell0.]

Halting is different from an FSM's accepting-state convention: this computation halts after changing the tape. The model can calculate or transform data, not only recognise input strings.

Tracing a machine

A hand trace records the state, scanned position and tape after each transition, including the transition that enters a halting state.

For the append machine, the initial tape has 1 in cells 0, 1 and 2 and blanks everywhere else. Start in qScan with the head at cell 0. Apply one matching rule at each step, writing before moving:

The final rule writes into cell 3 and then moves to cell 4. Stopping with the head on cell 3 omits the rule's movement. qH has no outgoing rule, so no fifth transition occurs. If n consecutive 1s encode the non-negative integer n in unary, this machine changes n to n+1. An initially blank tape therefore becomes one 1 and halts after one transition.

The rule table can be recovered from a diagram by reading each arrow. Conversely, turn each defined state/symbol pair in the table into the corresponding labelled arrow. The two representations must have identical read/write/move behavior. This example terminates because there are finitely many initial 1s and the head moves right until it finds the first blank. That argument concerns this machine and permitted inputs; it is not a proof that arbitrary machines halt.

Simulating transitions in Java

A Java simulator represents the machine's state and a finite visited part of its tape, then applies the formal transition rules in order.

public class Main {
    public static void main(String[] args) {
        StringBuilder tape = new StringBuilder("111_");
        int head = 0;
        String state = "qScan";
        while (!state.equals("qH")) {
            char read = tape.charAt(head);
            if (read == '1') {
                tape.setCharAt(head, '1');
                head++;
            } else if (read == '_') {
                tape.setCharAt(head, '1');
                head++;
                state = "qH";
            } else {
                throw new IllegalArgumentException("Invalid tape symbol");
            }
            if (head == tape.length()) {
                tape.append('_');
            }
        }
        System.out.println(tape);
        System.out.println(head);
    }
}