Difficulty: Intermediate | Prerequisites: Turing machines, decidability basics (EECS 376 Lectures 1-10)
Decidable languages are closed under union, intersection, complement, and set difference: combine decidable languages with any of these operations and the result is always decidable. Undecidable languages are not closed under these operations, so combining two undecidable languages (or mixing one with a decidable language) can go either way. Diagonalisation proves the power set of any countably infinite set is uncountably infinite, which in turn shows every countably infinite language contains undecidable subsets.
Decidable language
A language L for which there exists a Turing machine (decider) that halts on every input and correctly accepts strings in L and rejects strings not in L. In simple terms, a decidable language is one where you can always get a definite yes-or-no answer.
Undecidable language
A language for which no Turing machine exists that halts on every input and correctly decides membership. Think of it as a problem where no algorithm can guarantee it will finish and give the right answer for every possible input.
Set difference (A \ B)
The set of elements in A that are not in B: {x in A : x not in B}. In simple terms, you take everything in A and remove anything that also appears in B.
Complement of a language
The complement of L (written as the overline of L) is the set of all strings over the alphabet that are not in L. If L is decidable, its complement is also decidable (just swap accept and reject).
Power set P(A)
The set of all subsets of A. For a finite set with n elements, the power set has 2^n elements. For a countably infinite set, the power set is uncountably infinite.
Diagonalisation
A proof technique, originally due to Cantor, that constructs an element guaranteed to differ from every element in a supposed complete listing. The constructed element disagrees with the i-th listed element at position i. Think of it as building a counterexample row by row to show no listing can be complete.
Countably infinite
A set whose elements can be placed in a one-to-one correspondence with the natural numbers. The set of all Turing machines is countably infinite.
Uncountably infinite
A set that is too large to be listed in any one-to-one correspondence with the natural numbers. The real numbers are the classic example; the power set of any countably infinite set is another.
Decider
A Turing machine that halts on every input, either accepting or rejecting. Every decider recognises a decidable language.
Closure property
A class of languages is closed under an operation if applying that operation to languages in the class always produces another language in the class. Decidable languages are closed under union, intersection, complement, and set difference.
This is the bread and butter of exam questions on decidability. You are given languages combined with union, intersection, set difference, or complement, and told whether the component languages are decidable or undecidable. Your job: determine whether the result is always, sometimes, or never decidable.
If L1, L2, L3 are all decidable, then L = (L1 \ L2) ∩ L3 is always decidable.
Set difference of decidable languages is decidable: L4 = L1 \ L2 means "in L1 but not in L2." Since both have deciders, run each, accept only if M1 accepts and M2 rejects.
Intersection of decidable languages is decidable: L = L4 ∩ L3. Run both deciders; accept only if both accept.
The constructed decider M3 always halts because it only runs other deciders, each of which halts on every input.
The proof pattern: build a new TM that calls the existing deciders as subroutines. Because deciders always halt, the new TM always halts too, and it accepts exactly the right strings.
If L1 and L2 are both undecidable, L = L1 ∩ L2 is sometimes decidable.
To show "sometimes," you need two examples: one where the result is decidable and one where it is not.
Decidable case: Let L1 = L_HALT and L2 = the complement of L_HALT. Their intersection is the empty set, which is decidable (a TM that always rejects).
Undecidable case: Let L1 = L_HALT and L2 = L_ACC. Their intersection is L_ACC, which is undecidable.
If L1 is decidable and L2 is undecidable, L = L1 ∪ L2 is sometimes decidable.
Decidable case: Let L1 = Sigma* (all strings). Then L1 ∪ L2 = Sigma*, which is decidable regardless of L2.
Undecidable case: Let L1 = the empty set. Then L1 ∪ L2 = L2 = L_ACC, which is undecidable.
Operation | Components | Result |
|---|---|---|
(L1 \ L2) ∩ L3 | All decidable | Always decidable |
L1 ∩ L2 | Both undecidable | Sometimes decidable |
L1 ∪ L2 | L1 decidable, L2 undecidable | Sometimes decidable |
This section connects Cantor's diagonal argument to computability. The same technique that proves the reals are uncountable also proves that every countably infinite language harbours undecidable subsets.
For any countably infinite set A = {a1, a2, a3, ...}, its power set P(A) cannot be listed.
The proof proceeds by contradiction:
Assume you can list every subset of A as s1, s2, s3, ...
Build a table T where rows are subsets and columns are elements of A.
Entry T[i][j] = 1 if a_j is in s_i, and 0 otherwise.
Construct a new set x* by flipping the diagonal: x* contains a_j if and only if a_j is not in s_j.
x* differs from every s_i at position i, so x* is not in the list.
Contradiction: the listing was supposed to be complete.
This is exactly Cantor's diagonal argument, applied to subsets rather than decimal digits.
This follows from two observations:
The set of all Turing machines (deciders) is countably infinite, because each TM has a finite encoding.
The power set of a countably infinite language L is uncountably infinite (proved above), so L has uncountably many subsets.
Since there are only countably many deciders but uncountably many subsets, most subsets of L have no decider. Those subsets are undecidable.
The argument is a counting argument, not a construction: it tells you undecidable subsets exist without building one explicitly.
This result is why computability theory matters at all. It tells you that "most" languages (in a precise mathematical sense) are undecidable. The decidable ones are the exception, not the rule.
Students often assume that the intersection of two undecidable languages must be undecidable. It can be decidable (even empty). The key is to find concrete counterexamples in both directions.
Students sometimes claim a subset of a decidable language must be decidable. Subsets of decidable languages can absolutely be undecidable. Decidability is not inherited downward by taking subsets.
When asked to show "sometimes decidable," students often give only one example. You need two: one showing the result is decidable and one showing it is undecidable.
Students confuse "L4 is a subset of L1, therefore L4 is decidable" with a valid closure argument. Being a subset of a decidable language does not make a language decidable. The correct argument for L1 \ L2 being decidable is that you can build a decider using the deciders for L1 and L2.
⚠️ "Always, sometimes, or never decidable" is a standard exam format. Know the proof structure for each: always/never requires a general proof; sometimes requires two concrete examples.
⚠️ Decidable languages are closed under union, intersection, complement, set difference, and concatenation. This is frequently tested and assumed as background in later problems.
⚠️ The diagonalisation argument appears in multiple forms: Cantor's theorem on the reals, the undecidability of the halting problem, and the power-set proof here. Recognise the shared structure (construct an object that differs from every listed object at position i).
⚠️ The counting argument (countably many deciders vs. uncountably many subsets) is a favourite exam topic for showing existence of undecidable languages without constructing one.
True or False: The intersection of two decidable languages is always decidable.
True.
True or False: The union of a decidable language and an undecidable language is always undecidable.
False. If the decidable language is Sigma*, the union is Sigma*, which is decidable.
Fill in the blank: To show a language is "sometimes decidable," you must provide ______ examples.
Two: one where the result is decidable and one where it is not.
True or False: Every subset of a decidable language is decidable.
False. Subsets of decidable languages can be undecidable.
True or False: The power set of a countably infinite set is countably infinite.
False. It is uncountably infinite, by diagonalisation.
Q: Let L1 and L2 be decidable. Is L1 \ L2 always, sometimes, or never decidable? Justify.
A: Always decidable. Build a decider that runs the deciders for L1 and L2 on input x. Accept if M1 accepts and M2 rejects. Both deciders halt, so the new machine halts on every input.
Q: Let L1 be undecidable and L2 be decidable. Is L1 ∩ L2 always, sometimes, or never decidable?
A: Sometimes decidable. If L2 is the empty set, the intersection is empty (decidable). If L2 = Sigma* and L1 = L_HALT, the intersection is L_HALT (undecidable).
Q: Use diagonalisation to explain why P(N) is uncountably infinite.
A: Assume you can list all subsets of N as s1, s2, s3, ... Construct x* such that x* contains i if and only if i is not in s_i. Then x* differs from every s_i at position i, contradicting the assumption that the list is complete.
Q: Why does the existence of uncountably many subsets of a countably infinite language L imply that some subsets are undecidable?
A: There are only countably many Turing machines (each has a finite binary encoding). Each decider decides exactly one language. Countably many deciders cannot cover uncountably many subsets, so some subsets must lack a decider.
This material connects directly to Turing reductions: once you know which language classes are closed under which operations, you can use that knowledge to classify new languages by reducing them to known ones. It also ties into Rice's theorem, which generalises many undecidability results about properties of Turing machines.
The diagonalisation technique reappears throughout the course: in the proof that the halting problem is undecidable, in the time hierarchy theorem, and in showing the existence of languages not in P or NP.
Decidable, undecidable, closure properties, set difference, complement, intersection, union, always sometimes never decidable, diagonalisation, Cantor's diagonal argument, power set, countably infinite, uncountably infinite, L_HALT, L_ACC, Sigma star, decider, Turing machine, EECS 376, Foundations of Computer Science, computability theory