5 Supporting Lemmas
Before proving the main universality result, we establish several key lemmas that characterize how TM operations affect the encoded sequences.
The difference in encoding when writing at a position is \(0\) or \(\pm 2^k\) where \(k\) is the absolute value of the position.
One step of a TM changes the encoding by \(0\) or \(\pm 2^k\).
The \(k\) value in a sequence change equals the absolute position where the write occurred.
Movement constraint between \(k\) values: \(|k_j - k_i| \leq j - i\).
When the integer encoding difference equals zero, the same value was written.
Writing the same value as currently exists results in zero encoding difference.
If the sequence changes at time \(t\), then the machine hasn’t terminated at step \(t\).