A model of computation study guide

Build the model from its components

Start by identifying the finite set of states, the finite alphabet and the initial tape contents. Locate the start state and mark the current head position. Remember that the tape is divided into squares and is infinite in one direction, while the head reads and writes one square at a time. The machine's fixed program is expressed by its transition rules, so the next action depends on both the current state and the symbol being read.

For every transition, ask four questions in order:

1. What state is the machine currently in?
2. What symbol is under the head?
3. Which rule matches that state-symbol combination?
4. What symbol is written, where does the head move, and what is the next state?

Writing these details in a trace table reduces errors. Useful columns are: step number, current state, scanned symbol, symbol written, head movement, next state and the relevant tape section. After a write operation, update the tape before considering the next step. A later transition may depend on the changed symbol.

Moving between representations

To read a transition function, separate the input pair from the result. In δ(q1, a) = (q2, b, L), the machine starts in q1, reads a, changes to q2, writes b and moves left by one square. To construct a state transition diagram, draw an arrow from q1 to q2 and label it with the read symbol, written symbol and movement. To interpret a diagram, perform the reverse process: identify the current state, inspect the outgoing arrows and choose the one whose read symbol matches the symbol under the head.

A state with no outgoing transitions is a halting state. Therefore, when a trace reaches such a state, the correct conclusion is that the computation stops. Do not invent another step merely because there are still unused tape squares.

Exam application

In a hand-trace question, establish the initial configuration before applying any rule. Clearly distinguish the head position from the rest of the tape, and record the state after every transition. If a symbol is unchanged, still record the write operation where appropriate; failing to do so can make the reasoning unclear. If no transition applies, check whether the machine has reached a halting state or whether the trace has been misread.

In an explanation question, connect the parts of the model rather than listing them without purpose. The states represent the machine's current control situation, the alphabet limits the symbols it can use, the tape stores symbols in marked-off squares, and the read-write head interacts with one square at a time. The transition rules connect these components into a computation.

Self-check

After completing a trace, check that every move changes the head position by one square, every written symbol belongs to the stated alphabet, and every state change follows a listed rule. Check that the start state was used initially and that no further transition was performed after a halting state. Finally, explain in one or two sentences why the example is a computation described formally: its behaviour is determined by a finite set of states, symbols, tape operations and transitions. You should also be able to explain why a Universal Turing machine is significant: it extends the idea of a fixed machine by providing a general model capable of representing and carrying out the behaviour of other Turing machines.