Skip to content
Tutorials Center
My learning

Topics

Lesson 57 of 59 ยท Practice and Review

Practice: Turing Machines and Decidability

Practice problems on designing Turing machines, classifying languages as decidable, recognizable or neither, and writing reduction proofs, with machines verified by a Python simulator.

This lesson is a workout for the second half of the course: Turing machines, decidability, and reductions. It has three parts. First you design machines and test them with a simulator. Then you practice classifying languages as decidable, recognizable, or neither. Finally you write reduction proofs, which are the standard way to show a problem is undecidable.

Part 1: designing Turing machines

A good design starts with an algorithm in words, then breaks it into scans of the tape. The most common building blocks are: scan right to find a marker, scan left to return, replace a symbol by a marker so you never count it twice, and check at the end that no unmarked symbols remain.

Problem 1 (unary addition). The tape holds 1^m + 1^n. Replace the + by 1 and erase the last 1: the tape then holds 1^(m+n).

Problem 2 (decider). Decide { a^n b^n c^n : n โ‰ฅ 0 }. This language is not context-free, so no PDA can do it, but a Turing machine can: in each round, cross off one a (as X), one b (as Y) and one c (as Z). If all symbols are crossed off at the same time, accept.

The simulator is the same text-driven one from the Turing machine project: each rule is state symbol newstate write move, where the move is L, R or S, _ is blank and halt accepts. A missing rule rejects.

Python Two machines: unary addition and a^n b^n c^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 step counts for a^n b^n c^n grow quadratically: n rounds, each sweeping across the string. Tapes with more symbols or more tapes would improve this, but not past polynomial.

Part 2: classifying languages

Every language falls into one of four zones:

flowchart TD
    subgraph ALL["All languages (uncountably many)"]
        subgraph RE["Recognizable (Turing-recognizable, recursively enumerable)"]
            subgraph DEC["Decidable (recursive)"]
                P["P, NP, PSPACE, ..."]
            end
            ATM["A_TM, HALT: recognizable, not decidable"]
        end
        NOT["Not recognizable: complement of A_TM, EQ_TM, ..."]
    end

A language is decidable exactly when both it and its complement are recognizable.

Language Zone Why
A_DFA, A_CFG, E_DFA, EQ_DFA decidable simulate, or search the finite structure
E_CFG (does a grammar generate anything?) decidable mark nonterminals that can derive terminals
EQ_CFG undecidable cannot be decided in general
A_TM (does M accept w?) recognizable, undecidable simulate M on w, but cannot tell looping from slowness
HALT_TM recognizable, undecidable reduces from A_TM
complement of A_TM not recognizable if both were recognizable, A_TM would be decidable
E_TM (is L(M) empty?) undecidable, complement recognizable search for any accepted string
EQ_TM neither it nor its complement is recognizable much harder
REGULAR_TM (is L(M) regular?) undecidable by Rice's theorem

Why is a recognizable language recognized by "searching"? A recognizer may run forever on strings not in the language. Dovetailing lets one machine explore infinitely many possibilities fairly: run program 1 for one step, then programs 1 and 2 for one step each, then programs 1, 2, 3, and so on. Any program that halts will eventually be seen halting. The next program shows this idea with Python generators standing in for machines.

Python Dovetailing: recognizing without deciding

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 odd programs show up as halted, at different times (program 9 needs 81 steps). The even ones keep running. At no round can we say "this one will never halt", which is exactly why HALT is recognizable but not decidable.

Part 3: reduction proofs

To show a language B is undecidable, reduce a known undecidable problem A to B: assume a decider for B exists and use it to build a decider for A. The pattern is the same every time.

Problem 3. Show HALT_TM = { <M, w> : M halts on w } is undecidable.

Proof. Suppose a decider H for HALT exists. Build a decider for A_TM: on input <M, w>, run H on <M, w>. If H says M does not halt on w, reject. If H says M halts, simulate M on w (it must stop) and answer what M answers. This decides A_TM, which is impossible. So no H exists. โˆŽ

Problem 4. Show E_TM = { <M> : L(M) = โˆ… } is undecidable.

Proof. Suppose a decider R for E_TM exists. Given <M, w>, build a new machine M_w that on any input x ignores x, simulates M on w, and accepts if M accepts. Then L(M_w) is non-empty exactly when M accepts w. Run R on <M_w> and flip its answer: this decides A_TM. Contradiction. โˆŽ

Problem 5 (Rice's theorem). Any non-trivial property of the language of a Turing machine is undecidable. "Non-trivial" means some machines have the property and some do not. For example: "L(M) is finite", "L(M) contains the string 0101", "L(M) is regular", "L(M) = ฮฃ*". The proof pattern for each: pick a machine with the property and one without, and use M_w as above to embed A_TM.

Rice's theorem is about properties of the language a machine recognizes, not properties of the machine's behavior or structure. "Does M have more than 5 states?" is decidable (just count). "Does M ever move its head left on input 0?" is a question about behavior, and needs separate treatment.

Problem 6 (countability). Show that some language is not recognizable without exhibiting it. There are countably many Turing machines (each has a finite description) but uncountably many languages (the power set of ฮฃ*). So most languages have no machine at all.

Mapping reductions: a template

When asked for a proof that B is undecidable (or unrecognizable) via a mapping reduction A โ‰คm B:

  1. State the function f from instances of A to instances of B in words.
  2. Argue f is computable: describe a machine that outputs f(x).
  3. Prove x โˆˆ A โ‡” f(x) โˆˆ B, both directions.
  4. Conclude using the known status of A.

More problems to try

  1. Design a Turing machine that copies a string of 1s (1^n becomes 1^n # 1^n).
  2. Is { <M> : M accepts the string "hello" } decidable? Use Rice's theorem.
  3. Is { <M> : M has exactly 7 states } decidable? Why does Rice's theorem not apply?
  4. Show A_TM โ‰คm HALT_TM with an explicit function f.
  5. Show that if a language and its complement are both recognizable, the language is decidable (run both machines in parallel).
  6. Decide, with a justification, whether { <G> : G is a CFG with L(G) = ฮฃ* } is decidable.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which statement is true for a language L?

    Run the recognizers for L and its complement in parallel; exactly one will halt and accepts, which gives a decider. The converse is trivial.
  2. 2. Why does the reduction from A_TM to E_TM build a machine M_w that ignores its input?

    M_w simulates M on w regardless of its own input, so it accepts something exactly when M accepts w, tying emptiness to acceptance.
  3. 3. Rice's theorem does NOT apply to which question?

    That question concerns the machine description, not the language it recognizes, and is decidable by counting states.
  4. 4. Which language is not Turing-recognizable?

    If both A_TM and its complement were recognizable, A_TM would be decidable. It is not, so the complement is not recognizable.
  5. 5. Why does dovetailing let a recognizer handle infinitely many candidate computations?

    Interleaving gives each computation more and more steps; a halting one is found after a finite number of rounds, but a looping one is never ruled out.

Summary

  • Design Turing machines as a sequence of scans with markers, and test them on every short string.
  • Languages are decidable, recognizable but undecidable, or not even recognizable; a language is decidable iff it and its complement are recognizable.
  • Dovetailing recognizes without deciding.
  • Undecidability proofs reduce a known undecidable problem to the new one; Rice's theorem covers every non-trivial property of the recognized language.
  • Counting argument: countably many machines but uncountably many languages.

Next: Practice: Complexity Problems