Questions: Diagonalization and Uncomputability

Question 1

In the diagonalization argument for uncomputability, why is the constructed language D guaranteed to differ from every Turing machine's language?

• A. Because D is defined over a different alphabet than any Turing machine uses
• B. Because D is defined to include strings that no Turing machine can process
• C. Because D is defined so that for each Turing machine Mᵢ, the membership decision on string sᵢ is flipped — D differs from Mᵢ on exactly that string
• D. Because D contains uncountably many strings, and no TM can recognize an uncountable language

Answer: (C)

The power of diagonalization is in the targeted disagreement. We define: sᵢ ∈ D if and only if Mᵢ does *not* accept sᵢ. So D differs from M₁ on s₁ (flipped), from M₂ on s₂ (flipped), and from Mᵢ on sᵢ for every i. No Turing machine in the enumeration can recognize D, because the i-th machine disagrees with D on the i-th string. Option D is wrong — languages over a finite alphabet are always countable sets of strings.

Question 2

Why does a simple counting argument (there are uncountably many languages but only countably many TMs) prove something weaker than diagonalization?

• A. The counting argument only works for finite alphabets, while diagonalization works for any alphabet
• B. The counting argument proves that some unrecognizable languages exist, but doesn't exhibit a specific one; diagonalization constructs a concrete unrecognizable language
• C. The counting argument is logically invalid; only diagonalization gives a correct proof
• D. The counting argument requires the axiom of choice, while diagonalization does not

Answer: (B)

The cardinality argument is a pure existence proof: most languages have no TM, therefore at least one unrecognizable language exists. But 'at least one exists' is weaker than 'here is one.' Diagonalization gives a specific language D with an explicit, constructive definition — you can check whether any particular string is in D. This concrete construction is more useful for proving properties of specific languages and for reductions to other undecidability results. Both proofs are valid (option C is wrong).

Question 3

The diagonalization argument is specific to computation theory and has no counterpart in other areas of mathematics.

• T. True
• F. False

Answer: False

Diagonalization is a general mathematical technique. Cantor used the identical method in 1891 to prove the reals are uncountable: assume a complete list of reals, construct a real that differs from the n-th listed number in the n-th decimal digit. Russell's paradox uses the same diagonal logic. The uncomputability proof explicitly adapts Cantor's argument by replacing 'real numbers' with 'Turing machine languages' — the method is the same; only the domain changes.

Question 4

Uncomputability means that certain problems are unsolvable due to insufficient computational resources such as time or memory.

• T. True
• F. False

Answer: False

Uncomputability has nothing to do with resources — it is a mathematical absolute. An uncomputable language cannot be recognized by any Turing machine, running for any amount of time, with unlimited memory. The diagonalization proof imposes no resource bound; it shows that no algorithm of any kind can correctly decide membership. This is fundamentally different from computational complexity theory, which asks how much time or space a computable problem requires. An uncomputable problem would remain uncomputable even with arbitrarily powerful hardware.

Question 5

Explain why there must exist unrecognizable languages even without constructing one explicitly, using only a counting argument.

Model answer: Every Turing machine can be encoded as a finite string (listing its states, transitions, and tape alphabet), so the set of all Turing machines is countable. But a language is any subset of all strings, and the set of all subsets of a countably infinite set is uncountably infinite (by Cantor's theorem). So there are uncountably many languages but only countably many Turing machines. Since each TM recognizes exactly one language, TMs can cover only countably many languages — leaving uncountably many languages with no TM to recognize them.

This argument is elegant but non-constructive: it tells us most languages are unrecognizable without identifying any specific one. The diagonalization argument is stronger because it constructs a specific unrecognizable language D, which can then serve as a tool for proving other languages unrecognizable via reduction.