Integer Sequences from Turing Machine Tapes

3 The Basic Construction

We can now present our main construction, which converts Turing machine execution traces into integer sequences.

Definition 14 TM-to-Integer Encoding
#

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:

\[ s_t = \sum _{i \leq 0, T_t(i) = \text{true}} 2^{|i|} \]

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.