The diagonal argument shows that undecidable problems must exist because:

The set of all possible problems is uncountable, while the set of all possible programs is countable

There are more programs than problems

Every problem has infinitely many programs solving it

Programs cannot be written as finite strings

Russell's paradox and the standard proof of the halting problem's undecidability share:

Both are about finite automata only

In the Chomsky hierarchy, the language {aⁿbⁿ : n ≥ 0} is correctly classified as:

Context-free (its smallest/tightest class), not regular

Recursively enumerable but not context-sensitive

The Post Correspondence Problem (PCP) is significant chiefly because it:

Is itself undecidable and is used to prove many other undecidability results by reduction

Is always solvable in constant time

Whether two given context-free grammars generate the same language is:

The same question as asking if a DFA and NFA are equivalent

Only relevant to Turing machines

Which of the following are true of the relationship between decidability and tractability? (More than one option may be correct.)

Every NP-complete problem is decidable

No NP-complete problem is known to be efficiently (polynomial-time) decidable

Every NP-complete problem is decidable

No NP-complete problem is known to be efficiently (polynomial-time) decidable

Decidability and tractability are exactly the same property

The halting problem is intractable in exactly the same sense an NP-complete problem is

LALR(1) parsing, compared to canonical LR(1) parsing, is best described as:

The same construction with compatible states merged to shrink the parsing table

An entirely unrelated parsing technique from a different theory altogether

Only usable for regular languages, never context-free grammars

A technique with no table at all

Formal Language Foundations and Unsolvable Problems

Most of Unit 8 — regular and context-free languages, automata, Turing machines and undecidability, syntax and semantic analysis, runtime environments, intermediate code and optimisation — is taught in the course's Theory of Computation and Compiler Design chapters. This chapter covers what the unit adds at its opening: formal language foundations stated through diagonal-argument and Russell's-paradox reasoning before any automaton appears, and the Chomsky hierarchy and unsolvable-problems vocabulary (halting problem, Post correspondence problem, tractable and intractable) named explicitly.

Formal Languages, Non-Computational Problems, the Diagonal Argument and Russell's Paradox

Before any automaton is defined, the syllabus asks WHY 'non-computational' (unsolvable) problems must exist at all — a purely counting argument, owed to Cantor's DIAGONAL ARGUMENT. The set of all possible PROGRAMS (finite strings over a finite alphabet) is COUNTABLY infinite — they can be listed p₁, p₂, p₃, …, since each is a finite string. But the set of all possible FUNCTIONS from naturals to naturals (equivalently, all possible languages/problems one might want a program to solve) is UNCOUNTABLY infinite — strictly larger, by the same diagonal argument Cantor used to show the reals are uncountable. Since there are strictly more problems than there are programs to solve them, MOST problems have no program at all that solves them — undecidable/unsolvable problems are not a rare pathology to be found by clever construction, they are the overwhelming majority, and the diagonal argument proves this before any specific unsolvable problem (like the halting problem) is even named.

💡 Russell's paradox is the same self-reference trap in set theory

Consider the set R = {x : x ∉ x} — the set of all sets that do not contain themselves. Asking 'is R ∈ R?' leads to a direct contradiction either way: if R ∈ R, then by R's own defining rule R ∉ R; if R ∉ R, then R satisfies the rule and so R ∈ R. This is Russell's paradox, and it is the same SELF-REFERENCE mechanism the diagonal argument and the halting problem's own proof both exploit — a system powerful enough to talk about itself (a set that can contain itself, a program that can be given its own description as input) opens the door to this exact contradiction, which is precisely why it is placed alongside the diagonal argument as this syllabus item's shared conceptual root.

The Chomsky Hierarchy, Named Explicitly

The four Chomsky levels, strictly nested
Type	Language class	Recognising machine	Grammar restriction
Type 3	Regular	Finite automaton (DFA/NFA)	A → aB or A → a (right/left-linear)
Type 2	Context-free	Pushdown automaton	A → γ (single non-terminal on the left)
Type 1	Context-sensitive	Linear-bounded automaton	αAβ → αγβ (γ non-empty; length never decreases)
Type 0	Recursively enumerable / Unrestricted	Turing machine	No restriction at all on productions

⚠️ The hierarchy is STRICT containment, not four unrelated classes

Regular ⊊ Context-free ⊊ Context-sensitive ⊊ Recursively enumerable — each is a PROPER subset of the next, meaning every regular language is context-free, but not every context-free language is regular (e.g. {aⁿbⁿ : n ≥ 0} is context-free, provably not regular by the pumping lemma the course's chapter on it covers). A language's Chomsky TYPE is the SMALLEST class it belongs to — calling {aⁿbⁿ} 'context-sensitive' is technically true but not its tightest, and hence not its usually-intended, classification.

The Halting Problem, the Post Correspondence Problem and Other Unsolvable Problems

The Halting Problem asks: given a program P and an input x, does P halt on x, or run forever? Turing proved this UNDECIDABLE by a direct diagonal/self-reference argument: assume a hypothetical HALTS(P, x) decider exists, build a new program D that, given a program's own description P as input, runs HALTS(P, P) and then does the OPPOSITE (loops forever if HALTS says P halts on itself; halts if HALTS says P loops on itself) — then ask what D(D) does, and either answer contradicts what HALTS just decided. Since the assumption of a decider leads to contradiction, no such decider can exist. The Post Correspondence Problem (PCP) asks: given two lists of strings A = (a₁,…,aₙ) and B = (b₁,…,bₙ), is there a sequence of indices i₁,…,iₖ (repeats allowed) such that a_i1a_i2…a_ik = b_i1b_i2…b_ik? PCP is also undecidable, and it is USED to prove many OTHER undecidability results by reduction (showing that a decider for some new problem would give a decider for PCP), exactly the reduction technique from Lower Bound Theory applied here to undecidability rather than to a running-time lower bound.

Unsolvable problems for context-free languages: several natural questions that ARE decidable for regular languages become UNDECIDABLE once asked about context-free grammars — whether two context-free grammars generate the SAME language, whether a context-free grammar is AMBIGUOUS, and whether a context-free grammar generates ALL strings over its alphabet are all undecidable, in sharp contrast to the corresponding (decidable) questions for regular languages/DFAs.
Measuring and classifying complexity: the theory of computation's undecidability line (can it be solved AT ALL) is distinct from complexity theory's tractability line (can it be solved EFFICIENTLY) — a problem can be decidable yet still intractable (every NP-complete problem is decidable, since brute-force enumeration always eventually terminates for a finite input, but none is known to be efficiently decidable), and the vocabulary TRACTABLE/INTRACTABLE from the previous chapter is exactly the second, finer distinction drawn once a problem has already cleared the first, coarser decidability bar.

How Deep NET Goes: LALR(1) and Turing-Machine Variants

Two syllabus items are worth checking against what you study in the course's Compiler Design and Theory of Computation chapters. First, LALR(1) is named alongside LR parsing generally. It is the canonical LR(1) construction with the states that share a core merged to shrink the table — a small addition on top of LR theory you already know, not a separate topic. Second, the Turing-machine item names 'Standard Turing Machine and its Variations' and 'Construction of TM for Simple Problems'; both are standard material in the Turing-machine section of the Theory of Computation chapter. So, for Unit 8, study those chapters for the bulk of the unit and this chapter for the foundations that come before them.

Key takeaways

The diagonal argument shows there are strictly more possible problems (uncountable) than possible programs (countable), so most problems are unsolvable in principle — before any specific unsolvable problem is named.
Russell's paradox and the halting problem's proof both exploit the same self-reference mechanism.
The Chomsky hierarchy (regular ⊊ context-free ⊊ context-sensitive ⊊ recursively enumerable) is strict containment; a language's type is the smallest class it belongs to.
The halting problem and the Post Correspondence Problem are both undecidable; PCP is itself used to prove many other undecidability results by reduction.
Undecidability (can it be solved at all) and intractability (can it be solved efficiently) are distinct lines — every NP-complete problem is decidable, just not known to be efficiently so.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

The diagonal argument shows that undecidable problems must exist because:
1. The set of all possible problems is uncountable, while the set of all possible programs is countable
2. There are more programs than problems
3. Every problem has infinitely many programs solving it
4. Programs cannot be written as finite strings
Show answer
Answer: A — The set of all possible problems is uncountable, while the set of all possible programs is countable
Since programs (finite strings) are countable but functions/problems are uncountable, there are strictly more problems than there could ever be programs, so most problems have no solving program at all.
Russell's paradox and the standard proof of the halting problem's undecidability share:
1. The same self-reference mechanism
2. No relationship whatsoever
3. Both are about finite automata only
4. Both were disproven later
Show answer
Answer: A — The same self-reference mechanism
Both constructions consider an object applied to (or asking about) itself and derive a direct contradiction from either possible answer, which is the defining trick of self-reference used in both proofs.
In the Chomsky hierarchy, the language {aⁿbⁿ : n ≥ 0} is correctly classified as:
1. Context-free (its smallest/tightest class), not regular
2. Regular
3. Not a language at all
4. Recursively enumerable but not context-sensitive
Show answer
Answer: A — Context-free (its smallest/tightest class), not regular
{aⁿbⁿ} is generated by a context-free grammar but provably fails the pumping lemma for regular languages, so context-free is its tightest (and hence correct) classification, even though it is technically also context-sensitive and recursively enumerable.
The Post Correspondence Problem (PCP) is significant chiefly because it:
1. Is itself undecidable and is used to prove many other undecidability results by reduction
2. Is always solvable in constant time
3. Has nothing to do with strings
4. Was proven decidable in 1990
Show answer
Answer: A — Is itself undecidable and is used to prove many other undecidability results by reduction
PCP's undecidability, combined with how naturally it reduces to and from many other formal-language questions, makes it a standard anchor problem for proving other results undecidable by reduction.
Whether two given context-free grammars generate the same language is:
1. Undecidable
2. Decidable in constant time
3. The same question as asking if a DFA and NFA are equivalent
4. Only relevant to Turing machines
Show answer
Answer: A — Undecidable
Language equivalence for context-free grammars is undecidable, in sharp contrast to the corresponding question for regular languages/DFAs (deciding DFA/NFA equivalence is decidable, covered in the course's Theory of Computation chapter).
Which of the following are true of the relationship between decidability and tractability? (More than one option may be correct.)
1. Every NP-complete problem is decidable
2. No NP-complete problem is known to be efficiently (polynomial-time) decidable
3. Decidability and tractability are exactly the same property
4. The halting problem is intractable in exactly the same sense an NP-complete problem is
Show answer
Answer: A — Every NP-complete problem is decidable; B — No NP-complete problem is known to be efficiently (polynomial-time) decidable
Decidability (solvable at all, however slowly) and tractability (solvable efficiently) are distinct lines; an NP-complete problem is decidable by brute force but not known to be efficiently decidable, while the halting problem is not decidable at all, which is a strictly different (and stronger) kind of hardness than NP-completeness.
Name the mathematician whose diagonal argument (originally used to prove the reals are uncountable) is adapted to prove that there are more possible problems than possible programs.
Numerical answer — type the value.
Show answer
Answer: Cantor
Cantor's diagonal argument, originally a set-theory result about the uncountability of the reals, generalises directly to show the set of all functions/problems is uncountable while programs remain countable.
LALR(1) parsing, compared to canonical LR(1) parsing, is best described as:
1. The same construction with compatible states merged to shrink the parsing table
2. An entirely unrelated parsing technique from a different theory altogether
3. Only usable for regular languages, never context-free grammars
4. A technique with no table at all
Show answer
Answer: A — The same construction with compatible states merged to shrink the parsing table
LALR(1) builds on the same canonical-LR(1) machinery already covered in depth by the course's Compiler Design chapter, merging states with identical cores to produce a smaller table at a small cost in parsing power.