Skip to content
Tutorials Center
My learning

Topics

Lesson 36 of 59 ยท Turing Machines

Turing Machines for 0^n 1^n 2^n, w w^R and w w

Construct Turing machines for languages that need more than a stack: 0^n 1^n 2^n, even palindromes w w^R and the copy language ww. Python simulator and tests.

These are the languages that a pushdown automaton cannot handle but a Turing machine can: 0^n 1^n 2^n (three equal counts), w w^R (palindromes, which a PDA handles only by guessing) and w w (a copy, which a PDA cannot do at all). They are the standard exercises for learning how to match parts of a string on a tape. The central technique is always the same: cross off matching symbols one pair at a time, sweeping back and forth.

Language Context-free? Idea on the tape
0^n 1^n 2^n no mark a 0, a 1, a 2 per round
w w^R yes (needs a guess) match the first and last symbols, erase both, repeat
w w no find the middle, then match the i-th symbol of each half

0^n 1^n 2^n (n โ‰ฅ 1)

Each round marks one 0 as X, one 1 as Y and one 2 as Z, then returns to the left. When no 0 is left, the machine checks that only Ys and Zs remain.

flowchart LR
    q0(["q0: find 0"]) -->|"0 โ†’ X, R"| q1(("q1: find 1"))
    q1 -->|"1 โ†’ Y, R"| q2(("q2: find 2"))
    q2 -->|"2 โ†’ Z, L"| q3(("q3: go back"))
    q3 -->|"X โ†’ X, R"| q0
    q0 -->|"Y โ†’ Y, R"| q4(("q4: verify"))
    q4 -->|"_ โ†’ _, R"| qa((("qa")))

Loops over unmarked symbols and previous marks are left out. q4 accepts only if it sees nothing but Y and Z until the blank.

Python Turing machine for 0^n 1^n 2^n

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The machine is correct on all 9,841 strings tested. This is also why 0^n 1^n 2^n is context-sensitive: it needs no more space than the input, as the LBA lesson showed.

Even palindromes: w w^R

A pushdown automaton must guess the middle. A Turing machine can compare both ends directly. The strategy peel off both ends:

  1. Read the leftmost symbol, remember it in the state (q1 for 0, q2 for 1), and erase it.
  2. Run to the right end and look at the last symbol. If it differs from the remembered one, reject. If it matches, erase it too.
  3. Return to the left and repeat.
  4. If everything is erased, accept.

If the string has odd length, after erasing one end symbol the other end finds no partner (it reads a blank when it needs a symbol), and the machine rejects. This is how the machine checks for even length and the palindrome property in one go.

Python Turing machine for w w^R

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The rules for q3 and q5 are the only places where a comparison happens: q3 accepts a last symbol 0 (the first was 0), q5 accepts a last symbol 1. Every other case has no transition, so the machine rejects. This is the usual way to write a decider: spell out the good cases and let everything else fall off the table.

The copy language: w w

For w w we cannot peel off both ends: the first symbol must match the symbol at the middle, not the end. The machine therefore works in two phases.

Phase 1: find the middle. Sweep back and forth. In each sweep, mark the leftmost unmarked symbol as belonging to the left half (0 โ†’ X, 1 โ†’ Y) and the rightmost unmarked symbol as belonging to the right half (0 โ†’ P, 1 โ†’ Q). The marks keep the symbol's identity. If the string has odd length, the final left mark finds no unmarked cell on the right and the machine rejects.

Phase 2: compare the halves in order. Take the leftmost undone left mark (X or Y), replace it by D (done), remember which symbol it stood for, run right to the leftmost undone right mark and check that it has the same symbol; replace it by D. Repeat. If both halves are exhausted together, accept.

Writing 54 rules by hand is tedious and error prone, so the code generates the table with loops over the alphabet. This is how larger machines are built in practice.

Python Turing machine for the copy language ww

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The machine accepts 0101 and 110110 and rejects 0110: its halves are 01 and 10, so the second symbols differ and phase 2 finds no rule. The step count is quadratic in the input length, because each phase sweeps across the whole tape once per symbol.

Why is w w impossible for a PDA while w w^R is possible? A stack returns symbols in reverse order, which is exactly what w^R needs. A copy needs the same order, which would require a queue. A Turing machine has random access along the tape and is not bothered by the order.

Patterns to remember

  • Counting equal blocks: mark one symbol per block per round, return left, repeat; verify nothing unmarked is left.
  • Palindromes: erase from both ends, comparing.
  • Copies: first split the string in the middle by two-ended marking, then compare pairs.
  • Odd versus even length is detected for free by the two-ended marking.
  • Generate big rule tables from loops, and test them exhaustively on short strings.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How does the 0^n 1^n 2^n machine make sure that nothing is left unmatched at the end?

    Leftover 1s or 2s have no rule in q4, so the machine rejects.
  2. 2. Why does the w w^R machine reject strings of odd length?

    The matching step looks for a partner symbol and finds a blank instead; the missing rule rejects.
  3. 3. Why can't the 'peel both ends' strategy decide w w?

    In w w the i-th symbols of the two halves correspond; comparing ends would test w w^R instead.
  4. 4. What is the purpose of the marks P and Q in the w w machine?

    P and Q keep the identity of the symbol (0 or 1) while recording that the cell is part of the right half.

Summary

  • 0^n 1^n 2^n: mark one symbol of each block per round with X, Y, Z, and verify that nothing else remains.
  • w w^R: erase matching symbols from both ends; odd lengths fail automatically.
  • w w: split the string by marking from both ends, then compare corresponding symbols pair by pair.
  • A Turing machine can do all three, while a PDA can do the middle one only by guessing and cannot do the other two.
  • Build big machines by generating rules programmatically, and verify them exhaustively.

Next: Turing machines for sums and products