Undecidable Problems MCQ Practice

Question 1 of 10

Which statement describes an undecidable problem?

  1. A. Every algorithm finishes in one step
  2. B. The problem has a known linear-time solution for all inputs
  3. C. No algorithm can be constructed that always produces a correct yes-or-no answer for every input
  4. D. The only issue is that printers are offline

Question 2 of 10

A program intended to decide Problem Z loops forever on some inputs because of an infinite loop bug, even though a correct algorithm for Z exists. This situation is primarily:

  1. A. proof that all problems are undecidable
  2. B. proof that Z has no instances
  3. C. proof that Z is undecidable
  4. D. a defective implementation, not a proof of undecidability

Question 3 of 10

The stem states Problem W is undecidable. Which student claim is consistent with that fact?

  1. A. There might still be particular inputs for which a specialized method works
  2. B. A single Python program must answer W correctly for every input
  3. C. W cannot be written in English
  4. D. W must be a sorting problem

Question 4 of 10

Which example is decidable?

  1. A. Any problem that once had a buggy grader solution
  2. B. Determining whether an integer is divisible by 10 using MOD
  3. C. A problem the stem explicitly labels undecidable
  4. D. Any problem that a slow laptop struggles to finish today

Question 5 of 10

Efficiency problems and undecidable problems differ because:

  1. A. efficiency only applies to printers
  2. B. undecidable problems are always solved by counting to n
  3. C. efficiency assumes an algorithm exists and asks about resources; undecidability says no all-input algorithm exists
  4. D. they are synonyms in AP CSP

Question 6 of 10

Classification table:

Situation Best label
Correct algorithm exists; 2^n steps Efficiency concern
No all-input correct algorithm Undecidable
Wrong Boolean condition in IF ?

Best label for the third row?

  1. A. Heuristic success
  2. B. Proof of decidability
  3. C. Undecidable problem
  4. D. Program bug

Question 7 of 10

A heuristic fails on 5 percent of inputs but helps users most days. Which reading is best?

  1. A. Useful tools can still fail on some inputs without being a general decision algorithm
  2. B. Any failure rate means the problem cannot be stated
  3. C. Heuristics always prove undecidability
  4. D. Failure rates convert bugs into decidable proofs

Question 8 of 10

Do not assume a famous-sounding problem is undecidable unless the stem says so. Given only “Problem T asks whether a finite list of integers contains a duplicate,” which is justified?

  1. A. T is undecidable because hashing exists
  2. B. T is decidable by comparing elements with a clear finite process
  3. C. T is undecidable because lists are hard
  4. D. T is undecidable because one student’s code was slow

Question 9 of 10

Which claim mixes up categories?

  1. A. Calling a program slow when it needs many steps
  2. B. Calling a problem decidable when a correct all-input algorithm exists
  3. C. Calling a problem undecidable because a program has a null-pointer bug
  4. D. Calling a problem undecidable when no algorithm works for all inputs

Question 10 of 10

For an undecidable decision problem:

  1. A. every instance is answered in constant time
  2. B. all instances are syntax errors
  3. C. the only issue is screen brightness
  4. D. no algorithm answers every instance correctly