11.2 Computation Traces

A Turing machine does not compute in one large jump. It computes step by step. A computation trace records these steps.

Each step changes the machine from one configuration to the next.

A configuration contains all information needed to continue the computation:

Once these are known, the next step is determined by the transition function.

A configuration is often written by placing the current state next to the symbol under the head.

For example, suppose the tape contains:

and the head is reading the first symbol while the machine is in state $q_0$. We may write:

If the head is reading the third symbol, we may write:

This notation means that the state symbol marks the current head position.

One-Step Transitions

A one-step transition is written as:

This means configuration $C$ changes into configuration $C'$ in one machine step.

If:

then the machine does the following:

1. it reads $a$
2. it writes $b$
3. it moves right
4. it enters state $q'$

For example, if the current configuration is:

where $x$ and $y$ are strings, and the head reads $a$, then after moving right we get:

Here $b$ replaces $a$, and the state symbol moves one position to the right.

For a left move, if:

and the current configuration is:

then the next configuration is:

The symbol $b$ replaces $a$, and the head moves left onto the previous cell containing $c$.

Multi-Step Computations

A full computation is a sequence:

The initial configuration is $C_0$. It contains the input word, the start state, and the initial head position.

We write:

to mean that $C'$ is reachable from $C$ in zero or more steps.

So:

is always true, because zero steps are allowed.

If there is a sequence:

then:

Halting Traces

A computation halts when the machine reaches a halting state, such as:

or:

If the machine reaches $q_{\mathrm{accept}}$, we say it accepts the input. If it reaches $q_{\mathrm{reject}}$, we say it rejects the input.

A halting trace has finite length:

where $C_n$ is halting.

A non-halting trace is infinite:

In that case, the machine runs forever.

Example Trace

Consider the simple machine from the previous section. It scans right until it sees a blank.

Its rules are:

On input:

the trace is:

This trace shows the head moving right across the input. The tape contents do not change, but the position of the state symbol changes.

The final configuration contains $q_{\mathrm{halt}}$, so the computation stops.

Traces as Evidence

A computation trace is useful because it gives concrete evidence of what the machine does.

To show that a machine accepts an input, we can display a finite trace ending in:

To show that a machine rejects an input, we can display a finite trace ending in:

Showing that a machine never halts is harder. A finite trace can show only finite behavior. To prove non-halting, we need a general argument, such as showing that the machine repeats a pattern forever.

Determinism and Traces

For a deterministic Turing machine, each configuration has at most one next configuration.

So from a fixed input, there is only one possible trace:

This makes deterministic computation easy to reason about. There is no branching.

For nondeterministic machines, one configuration may have many possible next configurations. Then computation forms a tree rather than a single path. Deterministic machines are enough for the main computability theory developed here.

A computation trace is the operational view of a Turing machine. It turns the transition function into an explicit sequence of configurations, making the behavior of the machine visible one step at a time.