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 mark

Which of the following is the best-known example of an undecidable problem?

  • The halting problem — deciding whether any given program will eventually stop

  • Finding the largest value in a list

  • Sorting a list of numbers into ascending order

  • Performing a binary search on a sorted list

Choose your answer

2
1 mark

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 mark

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 mark

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 mark

Which of the following problems is decidable?

  • Determining whether a given whole number is a prime number

  • Determining, for any given program and input, whether that program will eventually halt

  • Determining whether any given program will run forever on a particular input

  • Determining whether any given program will halt for every possible input

Choose your answer