This material covers the computability half of the EECS 376 midterm: which problems can be solved by algorithms (decidability), which can be partially solved (recognizability), and which cannot be solved at all. You need to classify languages, prove decidability by constructing deciders, prove undecidability via Turing reductions, and reason about closure properties and countability.
Difficulty: Intermediate to Advanced
Prerequisites: a solid grasp of sets, functions, and proof by contradiction. You should know what a Turing machine is and be comfortable with the distinction between halting and looping before reading this.
Computability theory is the theoretical backbone of EECS 376. It addresses the question: "What can and cannot be computed?" The midterm tests three layers of this question. At the first layer, you classify specific languages as decidable, recognizable, or unrecognizable. At the second, you prove classifications correct, either by constructing a decider or by reducing a known undecidable language to the target. At the third, you reason about the structure of these classes: closure properties (what happens when you take complements, unions, intersections of decidable or undecidable languages) and countability (how many languages of each type exist).
This material connects to every other part of the course. Decidability questions often reference algorithms from the first half (Kruskal, Floyd-Warshall), and Turing reductions use the same proof-by-contradiction structure as correctness proofs for algorithms.
Decidable Language
A language L for which there exists a Turing machine (a decider) that halts on every input and correctly accepts strings in L and rejects strings not in L. In simple terms, a decidable problem is one where an algorithm can always give you a definite yes or no.
Recognizable (Recursively Enumerable) Language
A language L for which there exists a Turing machine that accepts every string in L but may loop forever on strings not in L. Think of it as: the machine can confirm membership but might never finish saying "no."
Unrecognizable Language
A language for which no Turing machine can even reliably say "yes" to all members. If a language is unrecognizable, it is also undecidable.
Turing Machine (TM)
The formal model of computation used in EECS 376. A TM reads symbols on a tape, changes state, and writes symbols according to a transition function. It can accept, reject, or loop.
Decider
A Turing machine that halts on every input (it never loops). Every decider is also a recognizer, but not every recognizer is a decider.
L_HALT
The halting language: {(M, x) : M is a TM and M halts on input x}. This is the canonical undecidable but recognizable language.
L_ACC
The acceptance language: {(M, x) : M is a TM and M accepts x}. Also undecidable but recognizable.
L_REJ
The rejection language: {(M, x) : M is a TM and M rejects x}. Also undecidable but recognizable.
Turing Reduction (<=_T)
A reduction showing that if problem B is decidable, then problem A is also decidable. Equivalently: if A is undecidable, then B is undecidable. In simple terms, you build a decider for A using a hypothetical decider for B as a subroutine.
Countable Set
A set that can be put in one-to-one correspondence with a subset of the natural numbers. The set of all Turing machines, all decidable languages, and all recognizable languages are countable.
Uncountable Set
A set that cannot be enumerated by the natural numbers. The set of all languages over {0, 1} is uncountable, and so is the set of all unrecognizable languages.
Complement of a Language
The complement of L (written L-bar) is the set of all strings not in L. If both L and L-bar are recognizable, then L is decidable.
A language is decidable if you can build a Turing machine that always halts (accepts or rejects) on every input.
Bounded simulation: if the question is "does M accept x within k steps?", you can simulate M for exactly k steps and give a definite answer. This is why L_281ACC = {(M, x) : M accepts x in strictly less than 282 steps} is decidable.
Finite languages are always decidable. Hard-code every string in the language into a decider. Example: the set of names of students in a specific course is finite, so it is decidable and recognizable.
Simple string properties are decidable. Example: "does x have at least as many 0s as 1s?" Just count and compare. The TM always halts because inputs are finite. Example: "is x socially distant?" (all 1s at least six positions apart). A single pass with a distance tracker decides it.
Every decidable language is recognizable (a decider is a special case of a recognizer).
A language is recognizable but not decidable when a machine can confirm "yes" instances but may loop on "no" instances. L_HALT and L_ACC are the standard examples.
If L is unrecognizable, then L is undecidable. The contrapositive: if L is decidable, then L is recognizable (since every decider is a recognizer).
The complement of a recognizable language is sometimes recognizable (when the language is decidable) and sometimes unrecognizable (when the language is recognizable but undecidable). This is because: if both L and L-bar are recognizable, then L is decidable.
The complements of some undecidable languages are unrecognizable (L_ACC-bar is unrecognizable), but not all (L_ACC is recognizable and is the complement of the undecidable L_ACC-bar).
To show A <=_T B: assume you have a decider R for B, and use it to construct a decider for A.
To show B is undecidable: reduce a known undecidable language A to B (A <=_T B). If B were decidable, then A would be too, contradiction.
L_HALT <=_T L_REJ (worked example): Assume R decides L_REJ. Construct decider H for L_HALT. Given (M, x), build M' that runs M on input w, then rejects. M' rejects w exactly when M halts on w. So R(M', x) accepts if and only if M halts on x.
L_ACC <=_T L_TuringSocialDistance (worked example): Assume S decides L_TuringSocialDistance = {M : L(M) = L_SocialDistance}. Given (M, x), build M' that on input w checks if w is in L_SocialDistance (using a decider D), then runs M(x). If M accepts x, M' accepts all socially distant strings (so L(M') = L_SocialDistance). If M does not accept x, M' rejects or loops on everything. Feed M' to S.
The key construction pattern: build a new machine M' whose behaviour depends on whether M accepts x, then feed M' to the hypothetical decider.
A decidable language is Turing reducible to any language (including undecidable ones), because you can build a decider for it without using the oracle at all. This means Mult <=_T MST is trivially true since Mult is decidable.
If A <=_T B and B is decidable, then A must be decidable. A cannot be undecidable in that case.
Decidable languages are closed under complement, union, and intersection.
The "crane" operator A crane B = A-bar union B-bar is decidable when A and B are decidable (by closure under complement and union).
Undecidable languages are not closed under union or intersection. Counterexample: L_HALT union L_HALT-bar = Sigma*, which is decidable. L_HALT intersect L_HALT-bar = empty set, also decidable.
A finite subset of an undecidable language is always decidable (finite languages are decidable).
A subset of a decidable language is sometimes decidable and sometimes not. Example: every language is a subset of Sigma*, which is decidable, but L_HALT is a subset of Sigma* and is undecidable.
The set of all Turing machines is countable (each TM has a finite encoding).
The set of all languages over {0, 1} is uncountable (by diagonalization).
The set of all recognizable languages is countable (each has at least one TM).
The set of all unrecognizable languages is uncountable: all languages minus recognizable languages. Since all languages are uncountable and recognizable languages are countable, and countable sets are closed under union, the remainder must be uncountable.
The set of all decidable languages is countable. The set of all C++ programs that never terminate is countable (each is a finite string).
Diagonalization cannot show the rationals are uncountable, because the rationals are provably countable.
A decidable language is Turing reducible to uncountably many languages (it reduces to every language, and there are uncountably many).
A TM with any finite number of tapes (29, 376, 1047) can be simulated by a single-tape TM. The number of tapes does not change which languages are decidable. A 1047-tape TM decides exactly the same languages as a 29-tape TM.
A TM given input x can accept, reject, or loop forever. It is false that a TM can only accept or reject. Only a decider is guaranteed to halt (accept or reject) on every input.
Language classification hierarchy
All decidable languages are recognizable. All recognizable languages are a subset of all languages. The complement of a recognizable-but-undecidable language is unrecognizable.
Closure properties summary
Class | Complement | Union | Intersection |
|---|---|---|---|
Decidable | Closed | Closed | Closed |
Recognizable | Not closed | Closed | Closed |
Undecidable | Not closed | Not closed | Not closed |
Turing reduction proof template
To show A <=_T B:
Assume R is a decider for B.
Construct a decider H for A using R as a subroutine.
Given input appropriate for A, build a new TM M' whose behaviour encodes the question about A.
Feed M' (and possibly an input) to R.
Show: if the input is in A, then R accepts, so H accepts. If the input is not in A, then R rejects, so H rejects.
Conclude: H decides A using R, so A <=_T B.
Students often think "undecidable" means "unrecognizable." It does not. L_HALT is undecidable but recognizable. Unrecognizable is strictly stronger.
A common error is assuming that the union or intersection of two undecidable languages must be undecidable. Counterexamples: L_HALT union L_HALT-bar = Sigma* (decidable), L_HALT intersect L_HALT-bar = empty set (decidable).
Students confuse "a Turing machine can only accept or reject" with the truth. A TM can also loop forever. Only a decider is guaranteed to halt.
On reductions, students sometimes get the direction backwards. A <=_T B means: "if B is easy (decidable), then A is easy." The undecidability flows in the opposite direction: "if A is hard (undecidable), then B is hard."
Students think more tapes means more computational power. It does not. Any multi-tape TM can be simulated by a single-tape TM. The languages decided are the same.
Expect multiple-choice questions asking you to classify a specific language as decidable, recognizable, or unrecognizable. The key test: can you build a machine that always halts? If the property depends on the runtime behaviour of an arbitrary TM (e.g. "does M accept string s?"), it is likely undecidable.
Bounded-simulation questions are a favourite: "M accepts x in fewer than 282 steps" is decidable; "M halts on x after at least 203 steps" is not (you cannot bound when halting occurs).
The True/False section tests closure properties. Know the counterexamples cold.
Written-answer problems require full Turing reduction proofs. Practise the template: assume a decider, construct M', feed it to the decider, argue both cases.
The "some" vs. "all" vs. "no" quantifier questions test nuance. "The complements of (all/some/no) undecidable languages are unrecognizable" requires you to produce examples in both directions.
True or False: If L is unrecognizable, then L is undecidable.
Fill in the blank: The set of all languages over {0, 1} is ___ (countable/uncountable).
True or False: A 376-tape Turing machine can decide languages that a single-tape TM cannot.
True or False: A finite subset of an undecidable language is always decidable.
Fill in the blank: If both L and L-bar are recognizable, then L is ___.
Answers: 1. True. 2. Uncountable. 3. False. 4. True. 5. Decidable.
Q: Is the language L_281ACC = {(M, x) : M accepts x in strictly less than 282 steps} decidable?
A: Yes. Simulate M on x for up to 281 steps. If M accepts within that time, accept. Otherwise reject. The simulation always terminates.
Q: Which of the following sets is uncountable: the set of all decidable languages, the set of all Turing machines, or the set of all unrecognizable languages?
A: The set of all unrecognizable languages. The set of all languages is uncountable, the set of recognizable languages is countable, and the difference (unrecognizable languages) must be uncountable since countable sets are closed under union.
Q: Show that L_HALT <=_T L_REJ, where L_REJ = {(M, x) : M rejects x}.
A: Assume R decides L_REJ. Build H for L_HALT: given (M, x), construct M' that on input w runs M on w, then rejects. M' rejects w exactly when M halts on w. Feed (M', x) to R. If R accepts, M halts on x, so H accepts. If R rejects, M loops on x, so H rejects. H decides L_HALT.
Q: Let A and B be decidable. Show that A crane B = A-bar union B-bar is decidable.
A: Since decidable languages are closed under complement, A-bar and B-bar are decidable. Since decidable languages are closed under union, A-bar union B-bar is decidable. Alternatively, construct a decider M: on input x, run the decider for A. If it rejects, accept. Run the decider for B. If it rejects, accept. Otherwise reject.
Q: The complement of a recognizable language is (always / sometimes / never) recognizable. Which is it?
A: Sometimes. If the language is decidable, its complement is also decidable (hence recognizable). If the language is recognizable but undecidable, its complement is unrecognizable.
Decidability questions often reference algorithms from the first half of the course. "Is {(T, G) : T is an MST of G} decidable?" requires you to know that Kruskal can compute an MST in finite time. Turing reductions use the same proof-by-contradiction structure as algorithm correctness proofs. The countability arguments (diagonalization) connect to the broader mathematical foundations of the course and to the question of why most problems are unsolvable.
EECS 376, Foundations of Computer Science, UMich, midterm review, decidability, decidable, undecidable, recognizable, unrecognizable, recursively enumerable, Turing machine, decider, recognizer, halting problem, L_HALT, L_ACC, L_REJ, acceptance language, rejection language, Turing reduction, mapping reduction, closure properties, complement, countable, uncountable, diagonalization, Cantor, multi-tape TM, Church-Turing thesis, Rice's theorem, finite language, bounded simulation