Integer Sequences from Turing Machine Tapes

5 Supporting Lemmas

Before proving the main universality result, we establish several key lemmas that characterize how TM operations affect the encoded sequences.

Lemma 18 Encoding Difference at Write

The difference in encoding when writing at a position is \(0\) or \(\pm 2^k\) where \(k\) is the absolute value of the position.

Lemma 19 Sequence Difference is Power of Two
#

One step of a TM changes the encoding by \(0\) or \(\pm 2^k\).

Lemma 20 K Value Equals Position
#

The \(k\) value in a sequence change equals the absolute position where the write occurred.

Lemma 21 Movement Constraint
#

Movement constraint between \(k\) values: \(|k_j - k_i| \leq j - i\).

Lemma 22 Encoding Difference Zero Implies Same

When the integer encoding difference equals zero, the same value was written.

Lemma 23 Same Value Zero Difference
#

Writing the same value as currently exists results in zero encoding difference.

Lemma 24 Sequence Change Implies Not Terminal

If the sequence changes at time \(t\), then the machine hasn’t terminated at step \(t\).