Turing Machines and Universality

The model has a finite set of states, a finite tape alphabet, a tape divided into cells, and a read/write head. The head observes one cell at a time. A transition specifies a new state, a symbol to write and a head movement, based on the current state and symbol.

One state is designated as the start. Under the convention used here, halting states have no outgoing rules. AQA examination questions use one tape infinite in one direction; follow the supplied boundary and movement conventions rather than assuming every textbook machine uses identical notation.

A transition can be written as (state,read)→(new state,write,move). First inspect the current cell, select the matching rule, write the replacement, move the head and update the state as specified. An unchanged symbol still counts as a deliberate write action in this notation.

For unary increment, represent n by n consecutive 1s followed by blanks. A scanning state moves right over each 1; on the first blank it writes another 1, moves right and enters Halt. The empty block represents zero in this chosen encoding.

A particular machine has a fixed finite rule table. A universal Turing machine can interpret encoded descriptions of other machines together with their inputs, rather than requiring a physically different rule table for each simulated task. This separates a general interpreter from the data describing a computation.

Turing machines provide a formal model for discussing what can be computed, independent of one programming language or commercial processor. They do not promise practical speed or decide every mathematical question. The Halting result still applies to unrestricted general computation under this model.

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.