Questions: Decidability and Undecidability

Question 1

A student concludes that because first-order arithmetic is undecidable, it is impossible to prove that '7 is prime' within arithmetic. What is wrong with this reasoning?

• A. Nothing — undecidability means no individual arithmetic sentence can be proved
• B. First-order arithmetic is actually decidable for simple sentences involving only bounded quantifiers
• C. Undecidability means no uniform algorithm decides ALL sentences; individual sentences like '7 is prime' can still have proofs
• D. The student confuses undecidability with inconsistency — undecidable theories prove both a sentence and its negation

Answer: (C)

This is the central misconception. Undecidability is a property of the collection of sentences — no single algorithm halts and correctly answers 'theorem or not?' for every input. But individual sentences can still have proofs found and verified: '7 is prime' has a straightforward formal proof, and Fermat's Last Theorem has a 200-page proof. Undecidability says we cannot automate the separation of all theorems from all non-theorems — not that no particular sentence is provable.

Question 2

Which statement correctly distinguishes a decidable theory from a semi-decidable one?

• A. A decidable theory has finitely many theorems; a semi-decidable theory has infinitely many
• B. In a decidable theory, an algorithm always halts with yes or no for every sentence; in a semi-decidable theory, the algorithm halts on theorems but may loop indefinitely on non-theorems
• C. Semi-decidability is a stronger property than decidability — semi-decidable theories have richer proof systems
• D. Decidable and semi-decidable are synonyms — both refer to theories with enumerable theorem sets

Answer: (B)

The key asymmetry: a decision procedure must terminate on ALL inputs with a correct yes or no. A semi-decision procedure only guarantees termination on theorems — it enumerates valid sentences but may loop forever on non-theorems, never producing a 'no.' First-order logic is semi-decidable: proof search will eventually find a proof if one exists, but it may run forever if the sentence is invalid. Option C reverses the relationship: decidability is strictly stronger — every decidable theory is also semi-decidable, but not vice versa.

Question 3

Propositional logic is decidable because truth tables provide a finite, always-terminating procedure to determine whether any propositional formula is a tautology.

• T. True
• F. False

Answer: True

A propositional formula has finitely many propositional variables. The truth table for n variables has exactly 2ⁿ rows — a finite number. Evaluating all rows is a mechanical procedure that always terminates. If every row gives True, the formula is a tautology; otherwise it is not. This is the canonical example of a decidable logic: no open cases, no infinite searches, guaranteed termination with a correct yes-or-no answer for every input formula.

Question 4

If a formal theory is undecidable, it should also be inconsistent — that is, it derives proofs of both a sentence and its negation.

• T. True
• F. False

Answer: False

Undecidability and inconsistency are completely independent properties. An undecidable theory lacks a uniform algorithm for deciding all sentences; an inconsistent theory derives a contradiction (proves both φ and ¬φ). First-order arithmetic is undecidable (Church's theorem) but consistent — it does not prove contradictions. Conversely, an inconsistent theory trivially 'proves' every sentence, making it degenerate but not in a useful sense of 'decidable.' The two properties do not entail each other in either direction.

Question 5

Explain what it means for a theory to be undecidable, without implying that nothing within the theory can be proved.

Model answer: A theory is undecidable if there exists no algorithm that, given any sentence of the theory as input, always halts and correctly outputs 'theorem' or 'not a theorem.' This is a claim about the non-existence of a uniform, general-purpose decision procedure for the entire collection of sentences — not a claim about any individual sentence. Many specific sentences in an undecidable theory are provable: a proof can be found, checked, and verified. Undecidability means we cannot write a program that reliably handles all sentences; it says nothing about whether particular proofs exist.

A useful analogy: 'no algorithm detects all malware' (undecidable) does not mean 'no malware can ever be identified.' Specific programs are identified all the time; the undecidability is about the impossibility of a general, always-correct solution for the universal case. Similarly, arithmetic truths are proved constantly — the infinitude of primes, Fermat's Last Theorem — but no algorithm correctly decides all of them. The undecidability result (via reduction from the halting problem) says the collection of arithmetic truths cannot be algorithmically separated from arithmetic falsehoods, even though any particular truth can be singled out and proved.