Contents > Abstract Machines > Turing Machine

Implementation

The following Turing machine implementation stores its data in an infinite array abstraction. The first N bytes of the array, a0‥aN−1, serve as an N-byte register, where a subset of those bytes store the state machine’s current state. The remaining bytes, aN‥a∞, emulate the tape drive, where each data byte, ti, is paired with a metadata byte, hi:

hi ≡ 1 if the head is over ti; otherwise, 0.

Initially, h0 = 1 and hi≠0 = 0, because the head starts out over t0.

To step the head, adjacent elements of h are swapped:

Since the array is bounded on the left, the tape is “folded in half at the origin” and the pairs are interlaced:

h0, t0, h−1, t−1, h1, t1, h−2, t−2, h2, t2, h−3, t−3, h3, t3, …

Every four bytes consists of a positive-indexed pair followed by a negative-indexed pair. Formally, for i ≥ 0:

aN+4i+0 ≡ hi

aN+4i+1 ≡ ti

aN+4i+2 ≡ h−(i+1)

aN+4i+3 ≡ t−(i+1)

At runtime, the machine slides the register to indices divisible by four. At those locations, j, it applies a transition function, Tm, that operates on the register bytes, aj‥aj+N−1, and eight extra bytes immediately to the right of the register, aj+N‥aj+N+7:

aj‥aj+N+7 ← Tm(aj‥aj+N+7)

The eight extra bytes correspond to the segment:

hj, tj, h−(j+1), t−(j+1), hj+1, tj+1, h−(j+2), t−(j+2)

Meaning, Tm has access to two consecutive positive-index pairs and two consecutive negative-index pairs. If the head is not among them (if metadata bytes hj, h−(j+1), hj+1, and h−(j+2) are all zero), then Tm passes its input through, unchanged. Otherwise, it uses the register value in conjunction with the data byte beneath the head to perform a state-transition table lookup. If the looked-up instructions command Tm to step the head to a metadata byte beyond the bounds of the eight extra bytes, then Tm cannot comply. In that case, Tm passes its input through, unchanged. Otherwise, it carries out the instructions. Specifically, it overwrites the data byte, it swaps two metadata bytes to step the head, and it modifies the register value to transition the state machine.

To enable Tm to know if it is being applied to the “fold” of the tape, where it may need to step the head from h0 to h−1 or vice versa, the first byte of the register, aj, is set to 1 if j = 0, and it is reset to 0, otherwise.

The MC program that governs the machine applies Tm to the minimal tape region guaranteed to contain the head. The head starts at h0, and during each cycle, it steps, at most, one element further away from that origin. This means, after y cycles, the minimal region expands to h−y‥hy. As shown below, the program slides the register back-and-forth across the array, applying Tm to every index divisible by four along the way, and venturing a greater distance out with each pass of the outer loop.

for i ← 4 to ∞ step by 4
  for j ← 0 to i−4 step by 4
    aj ← j = 0
    aj‥aj+N+7 ← Tm(aj‥aj+N+7)
    slideRegister(j, 4)
  for j ← i down to 4 step by 4
    aj ← j = 0
    aj‥aj+N+7 ← Tm(aj‥aj+N+7)
    slideRegister(j, −4)

Lines 2–5 slide the register rightward across the widening region. And lines 6–9 handle the return trip.

The following version expands slideRegister into nested loops that repeated swap array elements through the register.

for i ← 4 to ∞ step by 4
  for j ← 0 to i−4 step by 4
    aj ← j = 0
    aj‥aj+N+7 ← Tm(aj‥aj+N+7)
    for k ← 0 to 3
      for p ← N−1 down to 0
        [aj+k+p,aj+k+p+1] ← [aj+k+p+1,aj+k+p]
  for j ← i down to 4 step by 4
    aj ← j = 0
    aj‥aj+N+7 ← Tm(aj‥aj+N+7)
    for k ← 3 down to 0
      for p ← 0 to N−1
        [aj+k+p,aj+k+p+1] ← [aj+k+p+1,aj+k+p]

Through a chain of conversions from pseudocode to MC to TS to IL, that program ultimately represents an endless sequence of game inputs that can run any algorithm.