Turing Machine Examples

Turing Machine Examples

Let's build several Turing machines to understand how they compute. These examples show the step-by-step process of tape manipulation and state transitions.

Example 1: Recognize {0^n 1^n | n >= 1}

This TM matches each 0 with a corresponding 1 by repeatedly scanning the tape.

Algorithm:
  1. Replace the leftmost 0 with X
  2. Move right to find the leftmost 1
  3. Replace that 1 with Y
  4. Move left back to the next 0
  5. Repeat until all 0s are replaced
  6. If only Ys and blanks remain, accept

States:
  q0: looking for 0 to replace
  q1: moving right to find 1
  q2: moving left back to next 0
  q3: checking that only Ys remain

Transitions:
  q0: 0 → X, R, q1
  q0: Y → Y, R, q3   (all 0s replaced, check)
  q1: 0 → 0, R, q1   (skip 0s)
  q1: 1 → Y, L, q2   (found matching 1)
  q2: 0 → 0, L, q2   (skip 0s going left)
  q2: Y → Y, L, q2   (skip Ys going left)
  q2: X → X, R, q0   (found next 0)
  q3: Y → Y, R, q3   (skip Ys)
  q3: ␣ → ␣, -, qaccept  (end of tape, accept)

Example 2: Binary Addition

A TM that adds two binary numbers written on the tape in the format "a+b" (e.g., "110+11").

Algorithm:
  1. Start at the rightmost digit of the second number
  2. Add corresponding digits with carry
  3. Write the result digit
  4. Move left to the next pair
  5. Handle the carry at the end

Tape initially: 110+11␣␣␣
Step 1: 1+1 = 10, write 0, carry 1
Step 2: 1+1+carry(1) = 11, write 1, carry 1
Step 3: 1+carry(1) = 10, write 0, carry 1
Step 4: carry(1) at leftmost, write 1

Result: 1001 on tape

The TM reads the input, processes digits from
right to left, and writes the result.

Example 3: Palindrome Recognizer

A TM that checks if a string over {a, b} is a palindrome.

Algorithm:
  1. Mark the leftmost unmarked character
  2. Move right to find the rightmost unmarked character
  3. If they don't match, reject
  4. Mark the rightmost character
  5. Move back to the leftmost unmarked character
  6. Repeat until all characters are marked

States:
  q0: mark leftmost, remember it
  q1: move right to find rightmost unmarked
  q2: compare and mark
  q3: move left back
  q4: check if all marked

Transitions (for alphabet {a, b}):
  q0: a → X, R, q1    (remembered 'a')
  q0: b → X, R, q2    (remembered 'b')
  q0: X → X, R, q4    (all checked)
  q1: a → a, R, q1    (skip right)
  q1: b → b, R, q1
  q1: X → a?, L, q3   (found rightmost)
  ... and so on

Key Insight

Turing machines can compute anything computable. But they're slow in practice — they're theoretical models, not practical computers. Their value is in defining the limits of computation: what can and cannot be computed, and how much time/space is needed.