Question 1 of 5
(a) In one sentence, what does it mean that no algorithm works for all inputs? (b) Give a decidable problem about strings of finite length. (c) Explain why a slow correct algorithm does not make that string problem undecidable.
Responses receive AI feedback against a rubric after submission. Scores are practice estimates.
(a) In one sentence, what does it mean that no algorithm works for all inputs? (b) Give a decidable problem about strings of finite length. (c) Explain why a slow correct algorithm does not make that string problem undecidable.
The stem asserts Problem M is undecidable. Student A solves three instances by hand. Student B claims M is therefore decidable. (a) Critique Student B using the idea of all inputs. (b) What can be true about some instances of an undecidable problem? (c) What would Student B need to exhibit to show decidability?
For each case, write Undecidable, Efficiency, or Bug: (a) Correct algorithm exists; it performs n^5 steps. (b) Stem states no algorithm answers every input. (c) Algorithm exists, but the code returns the opposite Boolean by mistake. Then explain in one sentence why labeling (a) as undecidable would be wrong.
A spelling tool uses a heuristic that sometimes accepts a misspelled rare name. (a) Why can the tool still be useful? (b) Does those failures prove “spell-checking English” is undecidable? Explain. (c) Distinguish that situation from a stem that explicitly says a named decision problem is undecidable.
Problem F: “Is the sum of a finite list of integers negative?” (a) Describe a deciding algorithm. (b) If the algorithm runs slowly on a long list, is F undecidable? (c) If a programmer forgets to include the last element in the sum, what category is that mistake?