Let \(S = (s_0, s_1, \ldots , s_n)\) be a finite binary step sequence. We must construct a TM that generates it. This requires defining a valid head path \((p_0, p_1, \ldots , p_{n-1})\) that is consistent with the sequence properties.

First, we define the head path at moments of writing. Let \(I = \{ t \in [0, n-1] \mid s_{t+1} \neq s_t\} \), and let \(k_t = \log _2|s_{t+1} - s_t|\) for \(t \in I\). A consistent head path must have \(p_t = k_t\) for all \(t \in I\).

Next, we construct the full path by defining \(p_t\) for \(t \notin I\). Consider any two consecutive indices \(i, j\) in the augmented set \(I' = I \cup \{ -1, n\} \), where we define \(k_{-1} = 0\). For any \(t\) such that \(i {\lt} t {\lt} j\), we must define a path from \(p_i=k_i\) to \(p_j=k_j\) in \(j-i\) steps. By Definition 15.3(b), we know \(|k_j - k_i| \leq j-i\). This guarantees that such a path exists. For instance, a valid path moves one unit towards \(k_j\) for \(|k_j - k_i|\) steps, and then stays put for the remaining \(j - i - |k_j - k_i|\) steps. This constructs a complete and valid head path \((p_0, \ldots , p_{n-1})\) where \(|p_{t+1} - p_t| \leq 1\) for all \(t\).

With this path, we construct the TM. The TM has \(n+1\) states, \(q_0, \ldots , q_n\), where \(q_n\) is the halt state. For each \(t\) from \(0\) to \(n-1\), state \(q_t\) is designed to perform step \(t\) of the computation:

1. In state \(q_t\), the TM reads the bit at position \(p_t\).

2. If \(t \in I\), it writes ’1’ if \(s_{t+1} - s_t {\gt} 0\) and ’0’ if \(s_{t+1} - s_t {\lt} 0\). If \(t \notin I\), it writes back the same bit it read.

3. It moves the head according to the pre-defined path: left if \(p_{t+1}-p_t = -1\), right if \(p_{t+1}-p_t=1\), and no move if \(p_{t+1}-p_t=0\).

4. It transitions to state \(q_{t+1}\).

This machine, by construction, faithfully reproduces the sequence \(S\).