AP Computer Science Principles Quiz: Undecidable Problems

What this quiz covers

This quiz focuses on Undecidable Problems, giving you a quick way to practice the rules, question types, and explanations that matter most for AP Computer Science Principles.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

Question 1

1. An unreasonable-time problem
2. A heuristic problem
3. An optimization problem
4. A decidable problem (correct answer)

Explanation: This is the formal definition of a decidable problem. It focuses on the existence of a universally correct and terminating algorithm. The other options describe different classes of problems related to efficiency, approximation, or finding the best solution, rather than just determining a yes/no answer.

Question 2

1. It proves that there are fundamental limits to what can be achieved through computation and algorithms. (correct answer)
2. It implies that all important problems in computer science will eventually be solved with better technology.
3. It demonstrates that parallel computing is the only necessary path forward for solving the hardest problems.
4. It shows that heuristic algorithms are always less useful than algorithms that find an exact solution.

Explanation: The discovery of undecidable problems was a landmark in computer science because it established that there are clear, provable boundaries to what computers can solve algorithmically. It defined the limits of computation. Option (B) is the opposite of the implication. Options (C) and (D) are about strategies for difficult problems, not the fundamental meaning of undecidability.

Question 3

1. An algorithm exists to solve the problem, but it runs in an unreasonable amount of time on most inputs.
2. No single algorithm can be constructed that is guaranteed to provide a correct yes-or-no answer for all possible inputs. (correct answer)
3. The problem can only be solved using heuristic approaches that provide an approximate, but not exact, solution.
4. A solution to the problem requires more memory or processing power than is available on modern computer systems.

Explanation: The definition of an undecidable problem is one for which no algorithm can be constructed that always provides a correct yes-or-no answer for every possible input. The other options describe different types of difficult problems: (A) describes a problem that runs in an unreasonable amount of time, (C) describes an optimization problem often solved with heuristics, and (D) describes a problem limited by hardware, not by the theoretical limits of computation.

Question 4

1. A decidable problem, because for any one specific program and input, a person can simply run it to see the outcome.
2. An optimization problem, because it seeks the best or most efficient way to achieve the output "SUCCESS".
3. An undecidable problem, because no single algorithm can be constructed to give a correct yes-or-no answer for all cases. (correct answer)
4. A problem that requires a heuristic, because an exact determination is too complex for even the fastest modern computers.

Explanation: The problem as described is a classic undecidable problem. The stem explicitly states that no single algorithm can solve it for all cases, which is the definition of undecidability. The reasoning in (A) is flawed because if the program runs forever without printing "SUCCESS", you never get a definitive "no" answer. It is a yes/no decision problem, not an optimization problem (B). It is not about complexity or speed (D) but about theoretical computability.

Question 5

1. The problem is decidable, but the programmer's $CHECK_EQUALS$ algorithm is inefficient and needs to be optimized.
2. The problem is decidable, but the programmer's $CHECK_EQUALS$ algorithm contains a bug that causes an infinite loop on certain inputs.
3. The problem of determining program equivalence is undecidable, so no algorithm can work for all pairs of programs. (correct answer)
4. The problem is an optimization problem, and the programmer's $CHECK_EQUALS$ algorithm is a heuristic that is not always optimal.

Explanation: The problem of determining if two programs are equivalent for all inputs is a well-known undecidable problem in computer science. The behavior described—working for some cases but failing to terminate for others—is characteristic of an attempt to solve an undecidable problem. Therefore, the issue is the nature of the problem itself, not an inefficient or buggy implementation of a possible algorithm.

Question 6

1. Invest in research to create a new type of computer that is not bound by the theoretical limits of current machines.
2. Develop an algorithm that provides a correct solution for a specific, limited subset of inputs that are common in their business. (correct answer)
3. Abandon the project entirely, because it is a theoretical impossibility to make any useful progress on the problem.
4. Hire a team of mathematicians to find the complete algorithmic solution that computer scientists have overlooked.

Explanation: Since the general problem is unsolvable, a common and practical approach is to identify a useful, restricted version of the problem that is decidable and solve that instead. This provides value to customers without attempting the impossible. Options (A) and (D) misunderstand that undecidability is a proven theoretical limit. Option (C) is too pessimistic, as useful partial solutions often exist.

Question 7

1. The inherent theoretical limits of what can be determined by any possible algorithm. (correct answer)
2. The insufficient processing speed and memory capacity of current computing hardware.
3. The lack of a sufficiently expressive programming language to state a potential solution.
4. The high probability that a hardware error will occur during a very long and complex computation.

Explanation: Undecidability is a concept from the theory of computation that establishes fundamental limits on what algorithms can do. It is not a limitation of current hardware (B), programming languages (C), or the reliability of physical machines (D).

Question 8

1. The program would be too slow, as checking every possible behavior of a file would take an unreasonable amount of time.
2. The problem is undecidable, as perfectly predicting the behavior of an arbitrary program is not possible with a general algorithm. (correct answer)
3. The program would require an unreasonable amount of computer memory to store all known malware signatures.
4. The guarantee is only impossible if the files are encrypted, as encrypted files cannot be analyzed without the key.

Explanation: The general problem of predicting a program's behavior (in this case, whether it's malicious) is undecidable. This is a variant of the Halting Problem. No algorithm can exist that can analyze any arbitrary program and perfectly predict its behavior. Options (A) and (C) refer to practical limitations (time and memory), but the core issue is theoretical impossibility. Option (D) is a specific case, but the problem is undecidable even for unencrypted files.

Question 9

1. Undecidable problems had no correct answers, while NP-complete problems always had one answer.
2. Undecidable problems could not be decided by any always-correct terminating algorithm, unlike NP-complete problems. (correct answer)
3. Undecidable problems were solved by randomness, while NP-complete problems required strict determinism.
4. Undecidable problems were easier than NP-complete problems because they avoided worst-case inputs.

Explanation: This question tests understanding of undecidable problems in algorithms and programming (AP CSP). The key distinction between undecidable and NP-complete problems lies in whether they can be solved by any algorithm at all - undecidable problems have no algorithm that always terminates with a correct answer, while NP-complete problems do have algorithms (though they may be exponentially slow). The passage emphasizes that the Halting Problem is undecidable, meaning no algorithm can always correctly determine if a program halts, whereas NP-complete problems remain decidable despite being computationally expensive. Choice B is correct because it captures this fundamental difference: undecidable problems lack any always-correct terminating algorithm, while NP-complete problems have such algorithms even if they're inefficient. Choice D is incorrect as it reverses the relationship - undecidable problems are actually harder than NP-complete problems in that they cannot be solved at all. To help students: Use a hierarchy diagram showing P ⊆ NP ⊆ Decidable problems, with undecidable problems outside this hierarchy entirely.

Question 10

1. Undecidable problems were decidable but slower, while NP-complete problems were impossible to decide.
2. Undecidable problems lacked any always-correct terminating algorithm, while NP-complete problems still had one. (correct answer)
3. Undecidable problems were solved by heuristics, while NP-complete problems were solved instantly by compilers.
4. Undecidable problems came from hardware limits, while NP-complete problems came from software style choices.

Explanation: This question tests understanding of undecidable problems in algorithms and programming (AP CSP). The fundamental distinction between undecidable and NP-complete problems is that undecidable problems have no algorithm that can solve them for all inputs, while NP-complete problems do have algorithms (though potentially exponentially slow ones). The passage emphasizes that the Halting Problem is undecidable, contrasting it with NP-complete problems that remain decidable despite computational challenges. Choice B is correct because it precisely captures this distinction: undecidable problems lack any always-correct terminating algorithm, while NP-complete problems still have one (even if inefficient). Choice A is incorrect as it reverses the relationship - NP-complete problems are decidable but potentially slow, while undecidable problems are impossible to decide algorithmically. To help students: Create examples showing that you can write a brute-force algorithm for any NP-complete problem, but you cannot write any algorithm for the Halting Problem that works on all inputs.

Question 11

1. A problem for which a solution can always be found by a human, but not necessarily by a computer algorithm.
2. A problem for which an algorithm can be written to produce a correct output for all possible inputs. (correct answer)
3. A problem that has at least one instance that can be solved by an algorithm, even if other instances cannot.
4. A problem that can be solved in a reasonable amount of time, regardless of the size of the input data.

Explanation: A decidable problem is defined as a decision problem for which an algorithm can be created that will produce a correct output for all inputs. Option (C) is a characteristic of undecidable problems (some instances may be solvable). Option (D) confuses decidability with algorithmic efficiency (running in reasonable time). Option (A) is incorrect because decidability is specifically about algorithmic solvability.

Question 12

1. Algorithmic inefficiency, where some programs are too complex to analyze quickly.
2. A heuristic approach, where an exact answer is sacrificed for a faster approximation.
3. An undecidable problem, where some instances are solvable but no general algorithm exists for all instances. (correct answer)
4. A syntax error, where the rules of the programming language prevent a solution.

Explanation: This scenario describes the Halting Problem, a famous undecidable problem. The key aspect is that while specific instances can be solved, no single, general algorithm can solve it for all possible inputs (in this case, all possible programs). This is the definition of an undecidable problem. The other options are incorrect classifications.

Question 13

1. The problem can likely be solved, but it will require the development of much faster computer hardware.
2. An approximate solution to the problem may be found using a heuristic, but an exact general solution is possible with enough time.
3. No algorithm can ever be created that will solve all instances of the problem correctly, regardless of future technology. (correct answer)
4. Existing programming languages are not powerful enough to express an algorithm to solve the problem.

Explanation: A proof of undecidability is a fundamental, theoretical limit on computation. It means no algorithm can ever solve all instances of the problem, regardless of increases in computer speed, memory, or the invention of new programming languages. The limitation is inherent to the problem itself.

Question 14

1. An undecidable problem is one that has not yet been solved, while an unreasonable-time problem has been solved, but the solution is inefficient.
2. An undecidable problem has no algorithm that solves all of its instances, while an unreasonable-time problem has an algorithm for all instances, but it is too slow for practical use. (correct answer)
3. An undecidable problem can be solved if given an infinite amount of time, while an unreasonable-time problem can be solved in a finite, but very long, amount of time.
4. An undecidable problem requires parallel computing to solve, while an unreasonable-time problem can be solved on a single computer, just very slowly.

Explanation: This correctly separates the two concepts. Undecidability is a question of computability (can an algorithm exist at all for every case?), while unreasonable time is a question of complexity (an algorithm exists, but is it practical?). Option (A) is wrong because undecidable means proven unsolvable, not just unsolved. Options (C) and (D) present common misconceptions.

Question 15

1. Undecidability is a theoretical limit, meaning no correct algorithm can ever be designed, so computer speed is irrelevant. (correct answer)
2. Even with infinite speed, computers would lack the necessary memory to store the steps for solving an undecidable problem.
3. Undecidable problems often have an infinite number of possible inputs, which would still take an infinite amount of time to process.
4. Faster computers would only make it easier to find approximate solutions, not the exact answers required to solve the problem.

Explanation: This statement correctly identifies the core misconception. Undecidability means a correct, terminating algorithm for all instances does not exist. An infinitely fast computer running a non-existent algorithm is still unable to solve the problem. Speed cannot compensate for the lack of a method.

Question 16

1. Any algorithm that solves the problem must run in a reasonable amount of time.
2. An algorithm exists that can provide a correct yes-or-no answer for every possible input. (correct answer)
3. A heuristic algorithm exists that can provide a likely, but not guaranteed, answer for all inputs.
4. Some, but not necessarily all, instances of the problem can be solved by a known algorithm.

Explanation: This is the definition of a decidable problem. A problem can be decidable but still take an unreasonable amount of time to solve (A). A decidable problem has an exact algorithm, not just a heuristic one (C). The algorithm must work for all instances, not just some (D).

Question 17

1. It proves that certain problems are so complex they will always take an exponential amount of time to solve.
2. It establishes that no single algorithm can exist to analyze and correctly predict the complete behavior of all other algorithms. (correct answer)
3. It shows that today's computers lack the processing power to simulate the execution of every possible computer program.
4. It highlights the need for better programming languages that are designed to avoid the creation of infinite loops.

Explanation: The Halting Problem is significant because it's a problem about the behavior of algorithms that cannot be solved by any algorithm. This reveals a fundamental limitation: computation cannot perfectly analyze itself. Option (A) relates to efficiency, not undecidability. Option (C) incorrectly attributes the limit to hardware power. Option (D) misunderstands that the problem is theoretical, not language-specific.

Question 18

1. An unsolved problem might be decidable, but an algorithm has not been found yet; an undecidable problem is proven to have no general algorithm. (correct answer)
2. An unsolved problem is one that runs in unreasonable time, while an undecidable problem is one for which no algorithm is known.
3. An unsolved problem typically relates to processing large datasets, while an undecidable problem relates to abstract mathematical logic.
4. An unsolved problem can be solved with sufficient processing power, while an undecidable problem can be solved with sufficient computer memory.

Explanation: This statement correctly distinguishes between the current state of human knowledge (a problem is "unsolved") and a fundamental, proven property of the problem itself (it is "undecidable"). An unsolved problem may one day have an algorithm, but an undecidable problem never will. The other options introduce incorrect or irrelevant distinctions.

Question 19

1. A problem for which a very fast and efficient algorithm is already widely known and used.
2. A problem that has been successfully solved by an algorithm for millions of different test cases.
3. A problem that has only a finite number of possible inputs to consider. (correct answer)
4. A problem that can be solved using a large, distributed network of computers (crowdsourcing).

Explanation: If a problem has a finite number of possible inputs, an algorithm can be constructed to solve it. In the worst case, the algorithm could be a giant lookup table containing the correct answer for every single possible input. Since the number of inputs is finite, this lookup table is finite, and the algorithm is guaranteed to exist and terminate. The other options do not provide such a guarantee.

Question 20

1. The problem is decidable, because a solution has been found for at least one instance.
2. The problem is undecidable, because decidable problems do not have individual instances.
3. Nothing can be concluded, because decidability requires an algorithm that works for all instances. (correct answer)
4. The problem is likely decidable, but the algorithm might be inefficient on other instances.

Explanation: Solving one instance, or even many instances, of a problem does not prove that the problem is decidable. To be decidable, an algorithm must exist that can solve every possible instance of the problem. Undecidable problems can often have many solvable instances, so a single success proves nothing about the general case.