3 The Basic Construction
We can now present our main construction, which converts Turing machine execution traces into integer sequences.
Consider a Turing machine \(M\) with:
A tape unbounded to the left, with cells indexed by non-positive integers \(0, -1, -2, \ldots \)
A binary tape alphabet \(\{ \text{false}, \text{true}\} \)
An initial tape configuration where all cells contain \(\text{false}\)
A read/write head starting at position \(0\)
Let \(T_t(i)\) be the content of tape cell \(i\) at time step \(t \geq 0\). The integer sequence \((s_t)_{t \geq 0}\) generated by \(M\) is defined by:
We denote the head’s position at the beginning of step \(t\) (i.e., before the transition from \(t\) to \(t+1\)) as \(p_t\).
This sum is well-defined because a TM can only write on a finite portion of the tape in a finite number of steps.