Turing machines, decidability and recognizability
Goals and machine convention
Distinguish deciding a language from recognizing it and understand why common Turing-machine variants have the same computational power. Our deterministic TM has finite control, a tape unbounded in both directions, a head reading one cell, a finite tape alphabet Γ containing the input alphabet Σ and a blank not in Σ. Input occupies consecutive cells; the rest are blank. A transition reads a tape symbol, writes a symbol, changes state and moves one cell left or right. Accept and reject are distinct halting states. Stay-put moves or a one-way-infinite tape can be simulated and do not change the recognized or decidable languages.
A computation may accept, reject or run forever. L(M) consists only of inputs on which M eventually accepts. A recognizer must accept each member; on a nonmember it may reject or loop. A decider halts on every input and accepts exactly the members. “Recursive” means decidable; “recursively enumerable” (RE), “Turing-recognizable” and “semidecidable” refer to the recognizer class here.
1. Worked decider for a^n b^n c^n
First check the input is in abc*; reject otherwise. Repeatedly find the leftmost unmarked a and mark it X, then scan right to mark the leftmost unmarked b as Y and the leftmost unmarked c as Z. If a required b or c is absent, reject. Return to the left end and repeat. When no unmarked a remains, accept only if no unmarked b or c remains. Accept ε.
Trace aabbcc: the first round yields XaYbZc; the second yields XXYYZZ; the final scan accepts. For aabcc, the second round cannot find a fresh b and rejects. The initial ordering check prevents matching a word whose counts agree but symbols are interleaved.
Termination proof: each successful round marks one previously unmarked a; there are finitely many a symbols. Each scan stays within the finite input region, detected by surrounding blanks. A failed round halts immediately. Thus the machine halts on every input. This proves a non-context-free language can nevertheless be decidable; automaton memory restrictions and computability limits are different issues.
2. Recognition with simulation
Let A_TM={⟨M,w⟩:TM M accepts w}, using an effective finite encoding of machines and inputs. A universal simulator recognizes it by running M on w and accepting if M accepts. If M rejects, the simulator may reject; if M loops, it loops. Therefore recognition alone does not give a decider. Invalid encodings can be rejected by a finite syntax check. No fixed timeout proves rejection for all machines, because acceptance can occur arbitrarily late.
An enumerator prints strings, possibly with repeats, and need not halt. Its printed set is recognizable. To recognize membership, run the enumerator until the requested string appears; nonmembers may wait forever. Conversely, simulate a recognizer on all strings in dovetailed stages and print each that accepts. Do not run the simulations sequentially to completion, since the first may loop forever. The empty language is enumerated by a machine that never prints a word.
3. Decidability from two recognizers
L is decidable iff both L and its complement are recognizable. Forward: a decider recognizes L, and swapping its halting answers recognizes the complement. Reverse: run recognizers for L and its complement in alternating steps on input w. Exactly one must eventually accept because w belongs to exactly one of the two sets. Accept if the L machine accepts, otherwise reject when the complement machine accepts. The procedure always halts even if the other simulation runs forever.
Swapping accepting and rejecting states of an arbitrary recognizer does not generally recognize the complement: a nonmember on which it loops still loops. The all-input halting condition is what makes the complement trick valid for deciders.
4. Variants and class relationships
Multitape TMs can be simulated on one tape by encoding tape contents and head markers, sacrificing efficiency but not computability. Nondeterministic TMs accept when some finite branch accepts. A deterministic simulator explores their finitely branching computation tree breadth-first so that an infinite branch cannot hide an accepting finite branch. Thus deterministic and nondeterministic TMs recognize the same languages. This is a computability claim, not a claim of equal running time.
Fix a finite alphabet containing a,b,c, with effective machine/input encodings over that alphabet. Then regular ⊊ context-free ⊊ decidable ⊊ recognizable ⊊ all languages over that alphabet. The alphabet qualification matters: over a unary alphabet every context-free language is regular. Examples separating the first two inclusions are a^n b^n and a^n b^n c^n. A_TM separates decidable from recognizable, using the undecidability proof in Lesson 9. Its complement is not recognizable by the two-recognizer theorem. Do not confuse “not recognized by a DFA” with “not recognizable by a TM.”
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. A recognizer on a nonmember may:
A. Accept B. Reject or loop C. Always accept after a timeout D. Only halt in accept
Answer: B
A: Acceptance would incorrectly include the word.
B: Both behaviors are permitted for nonmembers.
C: A timeout cannot turn a nonmember into a member.
D: This would make all inputs members if it always halted that way.
P02. Which feature distinguishes a decider from an arbitrary recognizer?
A. Finite control B. Halting on every input C. A tape alphabet D. Acceptance of members
Answer: B
A: Both models use finite control.
B: A decider guarantees total termination.
C: Both have a tape alphabet.
D: Both must accept members.
P03. If L and its complement are both recognizable, L is:
A. Necessarily finite B. Decidable C. Necessarily regular D. Not recognizable
Answer: B
A: Infinite examples such as a* exist.
B: Dovetail the two recognizers and wait for one acceptance.
C: Decidable languages can be nonregular.
D: Recognizability was given.
P04. Why use breadth-first exploration of nondeterministic TM branches?
A. To make the tape finite B. To avoid getting trapped forever on one infinite branch C. To ensure every branch accepts D. To remove the input alphabet
Answer: B
A: The tape remains unbounded.
B: Every finite accepting branch is eventually explored.
C: Existential acceptance needs only one branch.
D: The alphabet is unchanged.
P05. The marking decider on aabcc rejects because:
A. The symbols are out of block order B. The second a cannot be paired with a fresh b C. It contains two c symbols D. Every length-five string is non-context-free
Answer: B
A: aabcc is in abc*.
B: There is only one b for two a symbols.
C: Two c symbols alone are not a rejection reason.
D: Context-freeness classifies languages, not individual lengths.
P06. Equivalent single-tape and multitape TM computability implies:
A. Identical running time on every input B. The same decidable and recognizable language classes C. Every language becomes regular D. All computations halt
Answer: B
A: Simulation may increase time substantially.
B: Tape organization changes efficiency, not these classes.
C: Finite-automaton power is much weaker.
D: Simulated machines can still loop.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Theory of Computation syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in