AP®Computer ScienceCollege BoardComputer Science PrinciplesExam QuestionsUnit 3: Algorithms and ProgrammingUndecidable Problems

Undecidable Problems (College Board AP® Computer Science Principles): Exam Questions

5 mins5 questions
1
1 point

The halting problem asks whether it's possible to write a program that can decide, for any given program and input, whether that program will eventually stop running. This is known to be an undecidable problem.

Why is the halting problem undecidable?

  • No algorithm exists that can correctly decide, for every possible program and input, whether that program halts

  • No computer has enough memory to store every possible program and check its behaviour

  • No programming language allows a program to examine its own source code

  • No program can run for an unlimited amount of time before being stopped by the operating system

Choose your answer

2
1 point

A student says: "An undecidable problem is just one that takes computers too long to solve right now." Why is this statement incorrect?

  • Undecidable means no algorithm can ever solve it correctly for all inputs, not that it is merely slow

  • Undecidable problems can always be solved quickly with a faster computer

  • Undecidable problems are the same as exponential-time problems

  • Undecidable problems have simply not been studied enough yet

Choose your answer

3
1 point

Which of the following best describes a decidable problem?

  • A problem for which a correct solution has already been discovered by researchers

  • A problem for which an algorithm exists that always gives a correct yes/no answer for every input and always terminates

  • A problem that can only be solved by the fastest available computers

  • A problem that no algorithm can solve correctly for some inputs

Choose your answer

4
1 point

A programmer builds a tool that correctly detects an infinite loop in many programs, but there are some programs for which it cannot give a correct answer. Which statement best explains this situation?

  • The programmer has proven that the halting problem is decidable

  • With enough additional effort, the tool could be extended to work correctly for every possible program

  • The tool must contain a bug, because detecting infinite loops is impossible for any program

  • The halting problem is undecidable, but partial solutions that work for specific programs are still possible

Choose your answer

5
1 point

A programmer writes an algorithm that takes any whole number, always reports correctly whether that number is even, and always finishes in a finite number of steps. What does this show about the problem the algorithm solves?

  • It is undecidable, because the algorithm would have to be run on every possible number

  • It is decidable, because an algorithm exists that gives a correct answer for every input and always finishes

  • It is undecidable, because no algorithm can be checked against every possible input

  • It is decidable only for the numbers the programmer has actually tested

Choose your answer