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\).