6 Universality Results
The definition of a finite binary step sequence is not just a property of TM-generated sequences; it is a complete characterization. Every finite sequence satisfying these conditions can be realized by a Turing machine.
Construct a Turing machine that generates a given finite binary step sequence.
Every finite binary step sequence is TM-generable.
Formalization Note: The theorem statement is complete and type-checks in Lean. The proof constructs an explicit Turing machine using states indexed by sequence position. The construction is complete except for the helper lemma construction_generates_sequence, which requires additional lemmas about machine state tracking through the computation. Specifically, we need to prove that after \(j\) steps, the machine is in state \(j\) with the head at the position specified by the constructed head path.
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:
In state \(q_t\), the TM reads the bit at position \(p_t\).
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.
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\).
It transitions to state \(q_{t+1}\).
This machine, by construction, faithfully reproduces the sequence \(S\).
Not every infinite binary step sequence is TM-generable.
Justification: While any finite prefix can be generated, a single, finite-state TM must generate the entire infinite sequence. An infinite binary step sequence could, for example, encode the solution to the Halting Problem by having its \(m\)-th write operation depend on the halting behavior of the \(m\)-th Turing machine. Such a sequence, while satisfying the local kinematic constraints, would not be computable and thus not generable by any single TM.
Note: This conjecture has not been formalized, as it is beyond the scope of the current project.