# 11.2 Computation Traces

## 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:

| Component     | Meaning                          |
| ------------- | -------------------------------- |
| current state | the machine’s internal state     |
| tape contents | the symbols written on the tape  |
| head position | the cell currently being scanned |

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:

$$
1011
$$

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

$$
q_0 1011
$$

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

$$
10q_0 11
$$

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

### One-Step Transitions

A one-step transition is written as:

$$
C \vdash C'
$$

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

If:

$$
\delta(q,a)=(q',b,R)
$$

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:

$$
xqay
$$

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

$$
xbq'y
$$

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

For a left move, if:

$$
\delta(q,a)=(q',b,L)
$$

and the current configuration is:

$$
xcqay
$$

then the next configuration is:

$$
xq'cby
$$

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:

$$
C_0 \vdash C_1 \vdash C_2 \vdash \cdots
$$

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

We write:

$$
C \vdash^* C'
$$

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

So:

$$
C \vdash^* C
$$

is always true, because zero steps are allowed.

If there is a sequence:

$$
C_0 \vdash C_1 \vdash \cdots \vdash C_n
$$

then:

$$
C_0 \vdash^* C_n
$$

### Halting Traces

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

$$
q_{\mathrm{accept}}
$$

or:

$$
q_{\mathrm{reject}}
$$

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:

$$
C_0 \vdash C_1 \vdash \cdots \vdash C_n
$$

where $C_n$ is halting.

A non-halting trace is infinite:

$$
C_0 \vdash C_1 \vdash C_2 \vdash \cdots
$$

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:

$$
\delta(q_0,0)=(q_0,0,R)
$$

$$
\delta(q_0,1)=(q_0,1,R)
$$

$$
\delta(q_0,\sqcup)=(q_{\mathrm{halt}},\sqcup,R)
$$

On input:

$$
1011
$$

the trace is:

$$
q_0 1011
\vdash
1q_0 011
\vdash
10q_0 11
\vdash
101q_0 1
\vdash
1011q_0 \sqcup
\vdash
1011\sqcup q_{\mathrm{halt}}\sqcup
$$

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:

$$
q_{\mathrm{accept}}
$$

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

$$
q_{\mathrm{reject}}
$$

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:

$$
C_0 \vdash C_1 \vdash C_2 \vdash \cdots
$$

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.