Undecidable Problems FRQ Practice

Responses receive AI feedback against a rubric after submission. Scores are practice estimates.

Question 1 of 5

(a) Define decidable problem in one sentence. (b) Define undecidable problem in one sentence. (c) Give one example of a decidable yes/no question about integers (state the algorithm idea briefly).

Question 2 of 5

The stem states Problem U is undecidable. A classmate writes a program that answers U on all even inputs and crashes on odd inputs. (a) Does this program show U is decidable? Explain. (b) What does AAP-style undecidability still allow about some instances? (c) Classify the crashes on odd inputs: undecidability proof, efficiency issue, or incomplete/buggy program behavior for a general solution?

Question 3 of 5

Compare three situations: 1. No algorithm exists that answers Problem P for every input. 2. An algorithm exists but needs about 2^n steps. 3. An algorithm exists but the coder swapped yes and no. (a) Label each as undecidable, efficiency, or bug. (b) Explain why (2) is still decidable. (c) Explain why (3) does not prove undecidability.

Question 4 of 5

A heuristic for Problem Q returns answers quickly and is correct on many classroom examples but fails on some crafted inputs. The stem does not claim Q is undecidable. (a) Can the heuristic still be useful? Explain. (b) Does failure on some inputs alone prove Q is undecidable? Explain. (c) What additional kind of fact would you need before calling Q undecidable in this course’s style?

Question 5 of 5

Problem D: “Does list nums contain a 0?” Assume nums is a finite list. (a) Outline an algorithm that decides D. (b) Why does a slow computer not make D undecidable? (c) If a student writes a loop that skips the last index by mistake, is that undecidability or a bug?