4 Structural Properties
The sequences generated by TMs are highly structured and defined by the physical movement of the TM head, which can only modify one bit each step, at one location each step, and move a single cell at each step.
A sequence \((s_t)_{t\geq 0}\) is a binary step sequence if it meets all of the following conditions:
\(s_0 = 0\).
For each step \(t \geq 0\), the difference \(\delta _t = s_{t+1} - s_t\) is either \(0\) or has the form \(\pm 2^k\) for some non-negative integer \(k\).
Let \(I = \{ t \geq 0 \mid \delta _t \neq 0\} \) be the set of indices where the sequence changes. For each \(t \in I\), define \(k_t = \log _2 |\delta _t|\). The following must hold:
For every \(t \in I\), we must have \(k_t \leq t\). This reflects that the head, starting at position 0, can reach at most position \(-t\) after \(t\) steps (moving leftward).
For any two indices \(i, j \in I\) with \(i {\lt} j\), we must have \(|k_j - k_i| \leq j - i\). This constrains the head’s movement between any two write operations.
These conditions lead to our first main result, which shows that all TM-generated sequences have this structure.
Every TM-generated sequence is a binary step sequence.
Let \((s_t)\) be a sequence generated by a TM according to Definition 14.
The initial tape is all zeros, so \(s_0 = \sum _{i=0}^\infty 0 \cdot 2^i = 0\).
At step \(t\), the TM is at position \(p_t\). It reads the bit \(b = T_t(p_t)\) and writes a new bit \(b'\). The change in the integer value is \((b' - b) \cdot 2^{p_t}\). Since \(b, b' \in \{ 0, 1\} \), this difference is either \(0\), \(2^{p_t}\) (if \(b=0, b'=1\)), or \(-2^{p_t}\) (if \(b=1, b'=0\)). This satisfies condition 2, with \(k = p_t\).
Let \(I\) be the set of steps with non-zero changes. For any \(t \in I\), the change occurs at the head position \(p_t\), so \(|s_{t+1} - s_t| = 2^{p_t}\). This implies \(k_t = p_t\) for all \(t \in I\). We must verify the conditions on \((k_t)\), which are now conditions on the head path \((p_t)\).
The head starts at \(p_0=0\) and at each step can move at most one position. Therefore, after \(t\) steps, its position \(p_t\) is at most \(t\). Thus, \(k_t = p_t \leq t\).
For any \(i, j \in I\) with \(i {\lt} j\), the head moves from position \(p_i\) to \(p_j\) in \(j-i\) steps. The maximum distance it can travel is \(j-i\). Therefore, \(|p_j - p_i| \leq j-i\). Substituting \(p_t=k_t\), we get \(|k_j - k_i| \leq j-i\).
Thus, any TM-generated sequence satisfies all conditions of a binary step sequence.
An immediate consequence of the definition is a tight bound on the growth of the sequence.
If \((s_t)_{t \geq 0}\) is a binary step sequence, then for any \(t \geq 0\), we have \(s_t {\lt} 2^{t+1}\).
At any time \(t\), the set of tape positions that could possibly have been written to are \(\{ 0, 1, \ldots , t\} \), since the head starts at \(p_0=0\) and can move at most one position per step. Therefore, for any \(i {\gt} t\), the tape cell at position \(i\) must contain its initial value of \(0\). The maximum possible value for \(s_t\) occurs if all reachable tape cells contain a ’1’:
Thus, \(s_t {\lt} 2^{t+1}\).