Undecidable Problems MCQ Practice

Question 1 of 10

A decidable problem is one for which:

  1. A. an algorithm exists that produces a correct answer for every input
  2. B. every program that attempts it runs forever on every input
  3. C. no computer can store the question text
  4. D. the problem has no instances

Question 2 of 10

An undecidable problem is best described as:

  1. A. a problem that has exactly one input
  2. B. a problem with no algorithm that always gives a correct yes/no answer for every input
  3. C. any program that takes more than one second
  4. D. a program with a typo in a variable name

Question 3 of 10

A student says, “My sorting program is slow on huge lists, so sorting is undecidable.” What is wrong?

  1. A. Only bugs create undecidable problems
  2. B. Nothing; slowness equals undecidability
  3. C. Slowness is about efficiency; undecidability means no algorithm works for all inputs
  4. D. Sorting cannot be stated as a problem

Question 4 of 10

The stem states that Problem H is undecidable. A student writes a program that answers H correctly on ten sample inputs. Which conclusion is valid?

  1. A. The program proves every possible input is solved
  2. B. Undecidable problems cannot have any solvable instances
  3. C. Problem H is actually decidable because ten inputs worked
  4. D. An undecidable problem may still have some instances solvable by a program, but no algorithm solves every instance

Question 5 of 10

Which scenario is about a bug, not undecidability?

  1. A. A program crashes because it divides by zero on an input the author forgot to handle
  2. B. No algorithm exists that answers a stated decision problem for every input
  3. C. A problem is proven to have no general algorithmic solution for all instances
  4. D. A decision problem has no procedure that always halts with the correct yes/no

Question 6 of 10

The table classifies claims.

Claim Category
No algorithm solves every instance Undecidable
Algorithm exists but needs huge time for large n Efficiency
Program returns wrong answer due to a logic error ?

What replaces the question mark?

  1. A. Undecidable
  2. B. Bug / incorrect program
  3. C. Decidable by definition
  4. D. Heuristic only

Question 7 of 10

A heuristic answers a hard decision problem quickly but is known to fail on some inputs. Which statement is true?

  1. A. Heuristics are identical to proofs of undecidability
  2. B. Failing on some inputs means the heuristic never helps
  3. C. The heuristic can still be useful even though it is not a correct algorithm for all inputs
  4. D. Any heuristic that fails once proves the problem is decidable

Question 8 of 10

Problem E asks: “Is the integer n even?” Which statement is correct?

  1. A. E is undecidable because numbers can be large
  2. B. E is undecidable because a buggy program once printed wrong output
  3. C. E has no instances
  4. D. E is decidable because an algorithm can check n MOD 2 for every integer n

Question 9 of 10

Which best separates “this program is slow” from “this problem is undecidable”?

  1. A. Slow concerns how many steps an algorithm takes; undecidable means no all-input correct algorithm exists
  2. B. They mean the same thing on every exam
  3. C. Slow programs are always undecidable problems
  4. D. Undecidable only means the code has long variable names

Question 10 of 10

If a problem is undecidable, then:

  1. A. all programs related to it have syntax errors
  2. B. there is no algorithm that works correctly for all inputs
  3. C. every instance is impossible to answer even by luck
  4. D. computers cannot display the problem statement