AP CSP - Undecidable Problems

The Halting problem is decidable.

• true

• false

An undecidable problem is one in which no algorithm can be constructed that always leads to a correct yes-or-no answer.

• true

• false

A team of programmers is designing software. One portion of the project presents a problem for which there is not an obvious solution. After some research, the team determines that the problem is undecidable. Which of the following best explains the consequence of the problem being undecidable?

• The problem can be solved algorithmically, but it will require an unreasonably long amount of time.

• The problem can be solved algorithmically, but it will require an unreasonably large amount of data storage.

• There is no possible algorithm that can be used to solve all instances of the problem.

• There are several different possible algorithms that can solve the problem, but there is controversy about which is the most efficient.

A student wants to determine whether a certain problem is undecidable. Which of the following will demonstrate that the problem is undecidable?

• Show that for one instance of the problem, an algorithm can be written that is always capable of providing a correct yes-or-no answer.

• Show that for one instance of the problem, no algorithm can be written that is capable of providing a correct yes-or-no answer.

• Show that for one instance of the problem, a heuristic is needed to write an algorithm that is capable of providing a correct yes-or-no answer.

• Show that for one instance of the problem, an algorithm that runs in unreasonable time can be written that is capable of providing a correct yes-or-no answer.

Which of the following best explains how algorithms that run on a computer can be used to solve problems?

• All problems can be solved with an algorithm that runs in a reasonable amount of time.

• All problems can be solved with an algorithm, but some algorithms might need a heuristic to run in a reasonable amount of time.

• All problems can be solved with an algorithm, but some algorithms might run in an unreasonable amount of time.

• Some problems cannot be solved by an algorithm.