Undecidable Problems
Help Questions
AP Computer Science Principles › Undecidable Problems
A problem is described as "a decision problem for which an algorithm can be constructed that always produces a correct yes-or-no answer for all possible inputs." What term does this definition describe?
An unreasonable-time problem
A heuristic problem
An optimization problem
A decidable problem
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.
What is the overall significance of the existence of undecidable problems for the field of computer science?
It implies that all important problems in computer science will eventually be solved with better technology.
It shows that heuristic algorithms are always less useful than algorithms that find an exact solution.
It proves that there are fundamental limits to what can be achieved through computation and algorithms.
It demonstrates that parallel computing is the only necessary path forward for solving the hardest problems.
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.
Which of the following is the defining characteristic of an undecidable problem in computer science?
The problem can only be solved using heuristic approaches that provide an approximate, but not exact, solution.
An algorithm exists to solve the problem, but it runs in an unreasonable amount of time on most inputs.
A solution to the problem requires more memory or processing power than is available on modern computer systems.
No single algorithm can be constructed that is guaranteed to provide a correct yes-or-no answer for all possible inputs.
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.
Consider the problem of determining if any given computer program, when run on any given input, will eventually print the word "SUCCESS". It has been proven that no single algorithm can be designed to solve this problem for all possible program-input pairs. What type of problem is this?
A decidable problem, because for any one specific program and input, a person can simply run it to see the outcome.
An undecidable problem, because no single algorithm can be constructed to give a correct yes-or-no answer for all cases.
An optimization problem, because it seeks the best or most efficient way to achieve the output "SUCCESS".
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.
A programmer creates a new software tool $$CHECK_EQUALS$$ that takes two programs as input. The tool can sometimes determine if the two programs produce the same output for all possible inputs, but for some pairs of programs, it runs forever without giving an answer. Which statement best explains this behavior?
The problem of determining program equivalence is undecidable, so no algorithm can work for all pairs of programs.
The problem is an optimization problem, and the programmer's $$CHECK_EQUALS$$ algorithm is a heuristic that is not always optimal.
The problem is decidable, but the programmer's $$CHECK_EQUALS$$ algorithm is inefficient and needs to be optimized.
The problem is decidable, but the programmer's $$CHECK_EQUALS$$ algorithm contains a bug that causes an infinite loop on certain inputs.
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.
A computer science problem has been proven to be undecidable. A company still needs a way to handle this problem for its customers. Which of the following is the most practical and common strategy for the company to adopt?
Invest in research to create a new type of computer that is not bound by the theoretical limits of current machines.
Abandon the project entirely, because it is a theoretical impossibility to make any useful progress on the problem.
Hire a team of mathematicians to find the complete algorithmic solution that computer scientists have overlooked.
Develop an algorithm that provides a correct solution for a specific, limited subset of inputs that are common in their business.
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.
A problem is determined to be undecidable. This means its fundamental unsolvability is due to which of the following?
The lack of a sufficiently expressive programming language to state a potential solution.
The high probability that a hardware error will occur during a very long and complex computation.
The insufficient processing speed and memory capacity of current computing hardware.
The inherent theoretical limits of what can be determined by any possible algorithm.
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).
A software company wants to create an antivirus program that guarantees it can analyze any file and provide a correct "yes" or "no" answer to the question: "Will running this file install malware?" Why is this guarantee impossible to fulfill from a theoretical computer science perspective?
The program would be too slow, as checking every possible behavior of a file would take an unreasonable amount of time.
The program would require an unreasonable amount of computer memory to store all known malware signatures.
The guarantee is only impossible if the files are encrypted, as encrypted files cannot be analyzed without the key.
The problem is undecidable, as perfectly predicting the behavior of an arbitrary program is not possible with a general algorithm.
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.
In a passage about software verification, undecidable problems were described as having no algorithm that always halted with a correct decision; the Halting Problem asked whether a program stopped; this blocked perfect analyzers; NP-complete problems were different because they remained decidable though sometimes slow. What makes undecidable problems distinct from NP-complete problems according to the text?
Undecidable problems could not be decided by any always-correct terminating algorithm, unlike NP-complete problems.
Undecidable problems were solved by randomness, while NP-complete problems required strict determinism.
Undecidable problems had no correct answers, while NP-complete problems always had one answer.
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.
In a verification-focused passage, undecidable problems were defined as having no algorithm that always halted with correct answers; the Halting Problem asked whether code stopped; this blocked perfect bug-finding; NP-complete problems differed because they stayed decidable though potentially slow. What makes undecidable problems distinct from NP-complete problems according to the text?
Undecidable problems were decidable but slower, while NP-complete problems were impossible to decide.
Undecidable problems came from hardware limits, while NP-complete problems came from software style choices.
Undecidable problems lacked any always-correct terminating algorithm, while NP-complete problems still had one.
Undecidable problems were solved by heuristics, while NP-complete problems were solved instantly by compilers.
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.